Circular Barn

Time limit2sMemory limit512 MB

Summary

Assign each cow waiting outside n rooms on a ring to a distinct room clockwise ahead so the sum of squared walking distances is as small as possible.

Level: Medium7 of 10
Topics: Greedy, Prefix sum
Solved: No attempts yet

Problem

Farmer John likes contemporary architecture, so he built a new barn in the shape of a perfect circle. Inside, $n$ rooms form a ring, numbered $1$ through $n$ clockwise around the perimeter of the barn ( $3 \le n \le 100000$ ). Every room has two doors to its neighboring rooms and one door to the outside of the barn.

Farmer John owns $n$ cows and wants exactly one cow to end up in each room. The cows line up at arbitrary outside doors, and several cows may pick the same door. Exactly $c_i$ cows stand outside the door of room $i$ , and $\sum c_i = n$ .

Farmer John herds them this way. Each cow enters through the door where she lined up, then walks clockwise through rooms until she reaches the room she will stay in. A cow that walks through $d$ doors spends $d^2$ energy. Find the smallest total energy the cows can spend when every room ends up with one cow.

Input

The first line contains $n$ . Each of the next $n$ lines contains one value, giving $c_1$ through $c_n$ in order.

Output

Print the smallest total energy the cows spend.

Examples2

Example 1
Input
```
10
1
0
0
2
0
0
1
2
2
2
```
Expected output
```
33
```
Example 2
Input
```
3
3
0
0
```
Expected output
```
5
```