Warehouse Allocation (Distribute)

One move takes a box from a non-empty pile and puts it on another pile. First make the difference between the largest and smallest final piles as small as possible; among plans that achieve this minimum difference, find the minimum number of moves. Initial counts may repeat.

输入格式

The first line contains n, and the second line contains n box counts. Original bounds: 1≤n≤100000, 1≤boxes[i]≤10^9; the total number of boxes stays the same, and no external difference parameter is given.

输出格式

Output a single integer answer.

样例 1

输入：

3
1 3 5

输出：

2

样例 2

输入：

2
5 5

输出：

0

样例 3

输入：

3
1 1 10

输出：

6

样例说明

The outputs of the three public examples are, in order: 2; 0; 6. Verified by independent enumeration or direct simulation.