近似相等 2

题目描述

给定整数序列 $A=(A_1,A_2,\dots,A_N)$。 你可以进行以下操作任意次(可以为 0 次):

选择满足 $1 \le i,j \le N$ 的整数 $i,j$。将 $A_i$ 减 1,并将 $A_j$ 加 1。

求使 $A$ 的最小值与最大值之差不超过 1 所需的最少操作次数。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

将答案作为整数输出。

样例

4
4 7 3 7

3

通过以下 3 次操作,可以使 $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)$。

无法用少于 3 次操作使 $A$ 的最大值与最小值之差不超过 1,因此答案为 3。

1
313

0

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

2499999974

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 输入均为整数