Equalizing Card Piles

There are $N$ piles of cards, numbered $1,2,\ldots,N$. Each pile contains a number of cards, and the total number of cards is a multiple of $N$. In one move, you can choose any pile and take any number of cards from it and then move them to an adjacent pile. Note that from pile $1$, you can only move cards to pile $2$, and from pile $N$, you can only move cards to pile $N-1$. For any other pile, you may move cards either to its left or its right neighbor.

Your task is to find a sequence of moves using the minimum number of moves such that all piles have the same number of cards.

For example, when $N=4$ and the piles have $9$, $8$, $17$, and $6$ cards respectively, one optimal sequence of moves is:

• Move $4$ cards from the 3^rd pile to the 4^th pile. Now the piles are: $9$, $8$, $13$, $10$.
• Move $3$ cards from the 3^rd pile to the 2^nd pile. Now the piles are: $9$, $11$, $10$, $10$.
• Move $1$ card from the 2^nd pile to the 1^st pile. Now the piles are: $10$, $10$, $10$, $10$.

The answer in this case is 3, which is the minimum number of moves required.

Hint: Let $a_i$ denote the number of cards in the $i$-th pile and let $\text{avg}$ be the average number of cards per pile. Define the difference $d_i = a_i - \text{avg}$ for each pile. Then, the prefix sums $S_i = d_1 + d_2 + \cdots + d_i$ (for $1 \le i < N$) indicate the imbalance that must be adjusted between adjacent piles. The minimum number of moves is the count of indices $i$ (from $1$ to $N-1$) for which $S_i \neq 0$.

inputFormat

The first line contains an integer $N$, the number of piles. The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$, where $a_i$ is the number of cards in the $i$-th pile. It is guaranteed that the total number of cards is divisible by $N$.

outputFormat

Output a single integer, which is the minimum number of moves required to equalize all the piles.

sample

4
9 8 17 6

3