题目描述

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

你是其中一位守护者，被委以重任来平衡整个王国。你将面临一个重要的任务：给定一个整数序列 $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≤N≤10^3，1≤A_i≤10^3$。

对于 60% 的数据，$1≤N≤10^3，1≤A_i≤10^9$。

对于 100% 的数据，$1≤N≤2×10^5，1≤A_i≤10^9$。