该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个神奇的王国里，存在着一种神奇的能量，它可以通过修改整数序列来改变世界的平衡。这个能量被称为"平衡世界的力量"，只有少数被选中的守护者可以掌握它。

你是其中一位守护者，被委以重任来平衡整个王国。你将面临一个重要的任务：给定一个整数序列 $A$ =($A_1,A_2,…,A_n$)，你需要使用你的力量进行操作，以使得序列 $A$ 的最大值和最小值之间的差值最多为 $1$。

你可以进行以下操作任意次数（包括零次）：

• 选择整数 $i$ 和 $j$，其中 $1≤i,j≤N$。将 $A_i$ 减 $1$，将 $A_j$ 增 $1$。

你的任务是找到使用"平衡世界的力量"所需的最少操作次数，以实现序列 $A$ 的平衡。

输入格式

第一行 $N$ ,表示数列的数值个数。

第二行 $N$ 个整数 $A_i$。

输出格式

输出最少操作次数。

样例数据

4
4 7 3 7

3

1
313

0

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

2499999974

样例说明

【样例 1 解释】

原始数列为 4,7,3,7。

将 $i=2$ 位置上的数减 $1$，$j=3$ 位置上的数加 $1$，数列 $A$ 变成 $4,6,4,7$。

将 $i=4$ 位置上的数减 $1$，$j=1$ 位置上的数加 $1$，数列 $A$ 变成 $5,6,4,6$。

将 $i=4$ 位置上的数减 $1$，$j=3$ 位置上的数加 $1$，数列 $A$ 变成 $5,6,5,5$。

【样例 2 解释】

原始数列，只有 $1$ 个元素，为 $313$ 。

不需要操作，即操作 $0$ 次即可。

数据范围

对于$30\%$数据，$1 \leq N \leq 10^3$,$1 \leq A_i \leq 10^3$,

对于$60\%$数据，$1 \leq N \leq 10^3$,$1 \leq A_i \leq 10^9$,

对于$100\%$数据，$1 \leq N \leq 2×10^5$,$1 \leq A_i \leq 10^9$,