Description

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

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

Find a way to move the cards so that all piles contain the same number of cards, using the minimum number of moves.

For example, when $N=4$, the numbers of cards in the $4$ piles are $9,8,17,6$.

It can be done in $3$ moves:

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

Input Format

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

Output Format

Output a single line: the minimum number of moves needed to make all piles equal.

4
9 8 17 6

3

Hint

Constraints: For $100\%$ of the testdata, $1 \le N \le 100$, $1 \le A_i \le 10000$.

Problem Source: NOIP 2002 Senior, Problem 1.

Translated by ChatGPT 5