Container Rearrangement

A yard at a port has $n$ slots in a row on its floor where containers can be stacked, and the yard currently holds $m$ containers. Every container has height 1, and there is no limit on how many containers a slot can hold. If $a_i$ ($1 ≤ i ≤ n$) is the number of containers stacked in the $i$-th slot, then $m = \sum_{i=1}^{n} a_i$ holds.

With no height limit, the counts in each slot can differ greatly, which can cause safety problems. So a crane moves some containers to other slots so that the height difference between any two slots is at most 1. That is, $|a_i - a_j| ≤ 1$ must hold for any $i$ and $j$. Containers can be moved only one at a time, and moving a container has no extra cost based on distance.

For example, in Figure 1, 35 containers are stacked in 8 slots, so $m = 35$ and $n = 8$. Rearranging them so that the height difference is at most 1 gives the result in Figure 2, and 5 containers must be moved.

Figure 1. Before rearrangement	Figure 2. Result of rearrangement

The first line contains a positive integer $n$ ($1 ≤ n ≤ 10^6$), the number of slots. The next line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$, the number of containers currently in each slot. The total number of containers $m$ satisfies $1 ≤ m ≤ 2 \times 10^9$.

Print, on one line, the minimum number of containers that must be moved to satisfy the condition.