Description

Mike家有n个钱仓，他们构成一个环，从1到n顺时针方向分布，也就是第i个钱仓会和第i-1个和第i+1个相邻，特别地，第n个钱仓和第1个钱仓相邻。

众所周知，Mike是个极其聪明的人，所以，他不会把钱全部放在同一个钱仓，它会平均分配，每个钱仓放1 块的钱。

在开始时，每个钱仓会有ci 块的钱，保证Σci=n，Mike会开着他的卡车将钱从一个钱仓顺时针运到一个钱仓。

由于是小型卡车，每次只能运1 块的钱，而且Mike要求每块钱最多只能运一次。

如果这块钱被运输且运输距离为d，那么Mike要付出d2的费用，问Mike付出的费用最少是多少。

Format

Input

第一行包含一个整数n。

接下来n行，描述ci。

n≤100000，Σci=n。

Output

仅包含一个整数，表示Mike最小付出的费用。

Samples

10
1
0
0
2
0
0
1
2
2
2

33