P1031 [NOIP 2002 Senior] Equalizing Cards

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$.

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 a single line: the minimum number of moves needed to make all piles equal.

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