给定一个整数序列 A=(A_1,A_2,\ldots,A_N)。你可以执行任意多次(也可以不执行)以下操作:选择两个整数 i 和 j(1 \le i,j \le N),将 A_i 减 1,并将 A_j 加 1。求使得序列 A 中的最大值与最小值的差不超过 1 所需的最少操作次数。
第一行一个整数 N。
第二行 N 个整数 A_1,A_2,\ldots,A_N。
输出一个整数 ans,表示所需的最少操作次数。
4 4 7 3 7
3
1 13
0
10 97 99 4 3 2 4 90 8 91 93
224
【数据范围】
1 \le N \le 2 \cdot 10^5;
1 \le A_i \le 10^9;
所有输入值均为整数;
输出答案 ans 满足 0 \le ans \le 2 \cdot 10^{14}。
【样例说明】
样例 1 中,通过以下三次操作可以使序列 A 的最大值与最小值之差不超过 1:选择 i=2 和 j=3,A 变为 (4,6,4,7)。选择 i=4 和 j=1,A 变为 (5,6,4,6)。选择 i=4 和 j=3,A 变为 (5,6,5,5)。无法在少于三次操作内使最大值与最小值之差不超过 1,因此答案为 3。