题目描述

有 $N$ 个箩筐，每个箩筐里面有若干个小球，个数分别是 $A_1$，$A_2$，$A_3...A_n$。

现在对这 $N$ 筐小球进行如下操作：随意选择其中任意两个箩筐 $i$ 个和第 $j$ 个箩筐里的小球个数 $A_i$ 和 $A_j$（$1≤i,j≤n$）分别进行 $A_i$ 加一，$A_j$ 减一的操作，即第 $i$ 个箩筐多放一个，第 $j$ 个箩筐拿走一个。试试求出至少需要多少次才能使得所有箩筐中个数最多的和个数最少的差值为 $1$。

输入格式

第一行，一个整数，表示 $N$，$1 \le N \le 2 \times 10^5$。

第二行，$N$ 个整数，以空格隔开，表示第 $i$ 个箩筐里的小球数量为 $A_i$，$1 \le A_i \le 10^9$。

输出格式

一行，一个整数，表示操作次数。

4
4 7 3 7

3

1
313

0

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

2499999974