Description

摆渡人，摆渡那些湮没在波涛中的灵魂。

摆渡人跟本杰明玩起了游戏，摆渡人把 $n$ 堆石子摆在本杰明面前并用 $1$ ~ $n$ 标号，其中第 $i$ 堆石子的数量为 $a_{i}$ 个，摆渡人允许本杰明做任意次操作。每次操作可以选择两堆石头 $i, j(1 \leq i, j \leq n)$，从第 $i$ 堆取出 $1$ 块石头并放入第 $j$ 堆石头中。摆渡人想让石头最多的一堆和最少的一堆之间的差值最小，试问本杰明的操作数最小是多少？

Format

Input

输入占两行，第一行 $n(1 \leq n \leq 10^{5})$ 个数，表示石头堆的数量第二行 $n$ 个数，第 $i$ 个数 $a_{i}(1 \leq a_{i} \leq 2^{30})$，表示第 $i$ 堆石头的数量

Output

输出一个整数，表示本杰明操作的最小次数

Samples

4
1 2 3 4

1

1
114514

0

4
2 2 6 7

4

Hint