Circular Barn

Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn is a ring of $n$ rooms, 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 also a door to the outside of the barn.

Farmer John wants exactly $r_i$ cows to end up in room $i$ ($1 \le r_i \le 100$). To herd the cows in without a mess, he unlocks the outside door of a single room, and every cow enters through that door. Each cow then walks clockwise through the rooms until she reaches the room she belongs in. The distance one cow walks is the number of interior doors she passes through. Farmer John wants to unlock the outside door that makes the total distance walked by all the cows as small as possible. Find that minimum total distance.

The first line contains $n$. Each of the next $n$ lines contains one integer, giving $r_1$ through $r_n$ in order.

Print the minimum total distance the cows walk.

In the first sample, the best choice is the outside door of the room that needs 7 cows.