## USACO 2016 February Contest, Bronze

## Problem 2. Circular Barn

Contest has ended.

**Log in to allow submissions in analysis mode**

Farmer John wants exactly $r_i$ cows to end up in each room $i$ ($1 \leq r_i \leq 100$). 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 FORMAT (file cbarn.in):

The first line of input contains $n$. Each of the remaining $n$ lines contain $r_1 \ldots r_n$.#### OUTPUT FORMAT (file cbarn.out):

Please write out the minimum total amount of distance the cows collectively need to travel.#### SAMPLE INPUT:

5 4 7 8 6 4

#### SAMPLE OUTPUT:

48

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

Problem credits: Brian Dean