【题目描述】

作为当代建筑的爱好者，农夫约翰建造了一个完美的圆形新谷仓。在谷仓内部，由n个房间组成的圈，围绕谷仓的周长顺时针从1…n开始编号(3≤n≤1000)。每个房间都有一扇通向相邻的两个房间的门，还有一扇门通向谷仓的外部。

农夫约翰有n头牛，他希望谷仓里的每个房间都有一头牛。然而，奶牛有点困惑，在任意的门前排队，可能有多头牛在同一扇门前排队。准确地说，奶牛排在房间的门外，因此∑ci=n。

为了管理牛群的放牧过程，使每个房间都有一头牛，农民约翰想使用以下方法:每头牛从它最初排队的那扇门进入，然后顺时针穿过房间，直到到达合适的目的地。假设一头牛走过d扇门需要消耗d2能量，请确定分配奶牛所需的最小能量，使每个房间都有一头奶牛。

【输入格式】(cbarn.in):

第一行输入一个整数n，其余n行中每一行包含一个整数c1…cn。

【输出格式】(cbarn.out)

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

【样例输入】:

10

1

0

0

2

0

0

1

2

2

2

【样例输出】:

33