Circular Barn (Bronze)

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of $n$ rooms, numbered clockwise from $\mathrm{1..}n$ around the perimeter of the barn. Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.

Farmer John wants exactly $r_i$ cows to end up in each room $i$. To herd the cows into the barn in an orderly fashion, he plans to unlock the exterior door of a single room, allowing the cows to enter through that door. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior door that will cause his cows to collectively walk a minimum total amount of distance. Please determine the minimum total distance his cows will need to walk, if he chooses the best such door to unlock. The distance walked by a single cow is the number of interior doors through which she passes.

Input

The first line contains $n(3\le n\le 1000)$. Each of the remaining $n$ lines contain $r_1,...,r_n(1\le r_i\le 100)$.

Output

Print the minimum total amount of distance the cows collectively need to travel.

Examples

In this example, the best solution is to let the cows enter through the door of the room that requires $7$ cows.