1839. 圆形牛棚

作为当代建筑的爱好者,农夫约翰建造了一个完美圆环形状的新牛棚。

牛棚内部有 $n$ 个房间,围成一个环形,按顺时针编号为 $1 \sim n$。

每个房间都既有通向相邻两个房间的门,也有通向牛棚外部的门。

约翰共有 $n$ 头奶牛,他希望每个房间里恰好有一头奶牛。

然而,奶牛们目前杂乱的在一些房间外面排起了队,其中,房间 $i$ 外面有 $c_i$ 头奶牛排队,$\sum{c_i} = n$。

为了使得每个房间恰好有一头奶牛,约翰希望采取如下方法:

每头奶牛从最初排队的房间的外门进入房间,然后顺时针穿过房间,直到到达合适的房间为止。

已知,一头奶牛如果穿过了 $d$ 扇门,则需要消耗 $d^2$ 的能量。(从外面进入初始房间不消耗能量)

请确定,为了使每个房间都有一头奶牛,所有奶牛需要消耗的总能量的最小值。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行,包含 $c_1,…,c_n$。

输出格式

输出所有奶牛消耗的总能量的最小值。

数据范围

$3 \le n \le 1000$

输入样例:

10
1
0
0
2
0
0
1
2
2
2

输出样例:

33

样例解释:

所有房间外的牛都进入到其排队的房间后,$1 \sim 10$ 号房间中奶牛的数量依次为 $1,0,0,2,0,0,1,2,2,2$。

一种可行的最佳方案为:

  1. 位于 $4$ 号房间的两头奶牛分别移动至 $5,6$ 号房间,消耗的总能量为 $1^2 + 2^2 = 5$。此时,各房间中奶牛的数量依次为 $1,0,0,0,1,1,1,2,2,2$。
  2. 位于 $1$ 号房间的奶牛移动至 $4$ 号房间,消耗的能量为 $3^2 = 9$。此时,各房间中奶牛的数量依次为 $0,0,0,1,1,1,1,2,2,2$。
  3. 位于 $10$ 号房间的两头奶牛分别移动至 $2,3$ 号房间,消耗的总能量为 $2^2+3^2=13$。此时,各房间中奶牛的数量依次为 $0,1,1,1,1,1,1,2,2,0$。
  4. 位于 $9$ 号房间的两头奶牛分别移动至 $10,1$ 号房间,消耗的总能量为 $1^2+2^2=5$。此时,各房间中奶牛的数量依次为 $1,1,1,1,1,1,1,2,0,1$。
  5. 位于 $8$ 号房间的其中一头奶牛移动至 $9$ 号房间,消耗的能量为 $1^2=1$。此时,各房间中奶牛的数量均为 $1$。

共消耗能量 $5+9+13+5+1=33$。