7687: USACO 2016 February Contest, Bronze —— Problem 2. Circular Barn
[Creator : ]
Description
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 $1…n$ around the perimeter of the barn ($3≤n≤1,000$). 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\ (1≤r_i≤100)$ 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 of input contains $n$. Each of the remaining $n$ lines contain $r_1…r_n$.
Output
Please write out the minimum total amount of distance the cows collectively need to travel.
Sample 1 Input
5
4
7
8
6
4
Sample 1 Output
48
In this example, the best solution is to let the cows enter through the door of the room that requires 7 cows.