作为当代建筑的爱好者，农夫约翰建造了一个完美圆环形状的新牛棚。
牛棚内部有 n 个房间，围成一个环形，按顺时针编号为 1∼n。
每个房间都既有通向相邻两个房间的门，也有通向牛棚外部的门。
约翰共有 n 头奶牛，他希望每个房间里恰好有一头奶牛。
然而，奶牛们目前杂乱的在一些房间外面排起了队，其中，房间 i 外面有 ci 头奶牛排队，∑ci=n。
为了使得每个房间恰好有一头奶牛，约翰希望采取如下方法：
每头奶牛从最初排队的房间的外门进入房间，然后顺时针穿过房间，直到到达合适的房间为止。
已知，一头奶牛如果穿过了 d 扇门，则需要消耗 d2 的能量。（从外面进入初始房间不消耗能量）
请确定，为了使每个房间都有一头奶牛，所有奶牛需要消耗的总能量的最小值。
第一行包含整数 n。
接下来 n 行，包含 c1,…,cn。
输出所有奶牛消耗的总能量的最小值。
数据范围
3≤n≤105
输入样例：
10
1
0
0
2
0
0
1
2
2
2
输出样例：
33
样例解释：
所有房间外的牛都进入到其排队的房间后，1∼10 号房间中奶牛的数量依次为 1,0,0,2,0,0,1,2,2,2。
一种可行的最佳方案为：
1、位于 4 号房间的两头奶牛分别移动至 5,6 号房间，消耗的总能量为 12+22=5。此时，各房间中奶牛的数量依次为 1,0,0,0,1,1,1,2,2,2。
2、位于 1 号房间的奶牛移动至 4 号房间，消耗的能量为 32=9。此时，各房间中奶牛的数量依次为 0,0,0,1,1,1,1,2,2,2。
3、位于 10 号房间的两头奶牛分别移动至 2,3 号房间，消耗的总能量为 22+32=13。此时，各房间中奶牛的数量依次为 0,1,1,1,1,1,1,2,2,0。
4、位于 9 号房间的两头奶牛分别移动至 10,1 号房间，消耗的总能量为 12+22=5。此时，各房间中奶牛的数量依次为 1,1,1,1,1,1,1,2,0,1。
5、位于 8 号房间的其中一头奶牛移动至 9 号房间，消耗的能量为 12=1。此时，各房间中奶牛的数量均为 1。
共消耗能量 5+9+13+5+1=33。
10
1
0
0
2
0
0
1
2
2
2 33