作为当代建筑的粉丝，农夫约翰建造了一个完美圆形的新谷仓。在内部，谷仓由 n 个房间组成，从谷仓周边的 1…n 顺时针编号 (3≤n≤1000)。每个房间都有通往相邻两个房间的门，还有一扇通往谷仓外部的门。农夫约翰拥有 n 头奶牛，他希望谷仓的每个房间里只有一头奶牛。然而，有些困惑的奶牛在门口随意排着队，可能有多头奶牛在同一个门口排着队。准确地说$c_i$​​​奶牛在房间 i 的门外排队，所以 ∑$c_i​​​$=n。

为了管理放牧奶牛的过程，让每个房间里都有一头奶牛，Farmer John 想要使用以下方法：每头奶牛从她最初排队的门进入，然后顺时针穿过房间，直到她到达一个合适的目的地。假设一头牛穿过 d 扇门消耗 $d^2$能量，请确定分配奶牛所需的最低能量，以便每个房间都有一头奶牛。

输入格式（文件 cbarn.in）：

输入的第一行包含。剩下的 n 行中的每一行都包含 $c_1​​​…c_n​​$.

输出格式（文件 cbarn.out）：

请写出奶牛消耗的最低能量。

SAMPLE INPUT:

10
1
0
0
2
0
0
1
2
2
2

SAMPLE OUTPUT:

33