Circular Barn (Silver)

Farmer John has built a new barn shaped as a perfect circle. Inside, $n$ rooms form a ring, numbered $1$ through $n$ clockwise around the perimeter of the barn ($3 \le n \le 1000$). Each room has a door to each of its two neighboring rooms, and one more door that opens 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 of them may pick the same door. Exactly $c_i$ cows line up outside the door of room $i$, and $\sum c_i = n$. Every $c_i$ is a nonnegative integer.

To get one cow into each room, Farmer John uses this procedure. Each cow enters through the door where she lined up, then walks clockwise from room to room until she reaches the room she is assigned to. A cow that walks through $d$ doors spends $d^2$ energy. Find the smallest total energy the cows can spend while filling every room with exactly one cow.

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

Print the smallest total energy the cows spend.