Dividing Cards Equally

Problem Description

There are $N$ piles of cards, numbered $1, 2, \ldots, N$. Each pile has some number of cards, but the total number of cards must be a multiple of $N$. You may take some cards from any pile and then move them.

The moving rule: cards taken from pile $1$ may only be moved to pile $2$; cards taken from pile $N$ may only be moved to pile $N-1$; cards taken from any other pile may be moved to the adjacent pile on the left or on the right.

Now find a moving method that makes the number of cards in each pile equal, using the fewest moves.

For example, when $N=4$, the $4$ piles have $9, 8, 17, 6$ cards respectively.

It takes $3$ moves to reach the goal:

• Take $4$ cards from the third pile and put them on the fourth pile; now the piles are $9, 8, 13, 10$.
• Take $3$ cards from the third pile and put them on the second pile; now the piles are $9, 11, 10, 10$.
• Take $1$ card from the second pile and put it on the first pile; now the piles are $10, 10, 10, 10$.

Input Format

The first line is a single integer $N$, the number of piles. The second line has $N$ integers $A_1, A_2, \ldots, A_N$, the initial number of cards in each pile.

Output Format

One line, the minimum number of moves needed for all piles to become equal.

Sample Input

4
9 8 17 6

Sample Output

3

Hint

For $100\%$ of the data, $1 \le N \le 100$, $1 \le A_i \le 10000$.

【题目来源】 NOIP 2002 Advanced Group, Problem 1.