Get Fewest Operations (Box Balancing)

One move takes a box from a non-empty pile and puts it on another pile. First, the difference between the largest and smallest final piles must reach its smallest possible value; then find the minimum number of moves needed to achieve it.

输入格式

The first line contains n (1..100000), and the second line contains n box counts (1..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

4
5 5 8 7

输出：

2

样例 2

输入：

2
1 1

输出：

0

样例 3

输入：

2
1 5

输出：

2

样例说明

Example 1: the total is 25 and the sorted target is 6, 6, 6, 7; move 2 boxes out of the pile of 8, one to each 5, for 2 moves in total. Example 2: already balanced, 0 moves. Example 3: move 2 boxes from 5 to 1, making the two piles 3, 3, for 2 moves.