思路：模拟

显然，要让极差最小，只需要将所有数都靠近平均值就行了。

如果所有数都可以变成平均值，那么极差为0，否则极差为1。

设平均值为$x$(向下取整)，当极差为1时，数组为若干个$x$和若干个$x+1$

题目描述

小乖有一个长度为 n 的数组,每次操作可以选择两个下标i和j,将 $a_j$ 减去 1, 将 $a_j$ 加 上1,小乖想知道最少需要多少次操作，可以使数组极差最小。

数组的极差为数组中最大值和最小值的差

输入描述

$第一行输入一个整数 n (2 ≤ n ≤ 10^5), 表示数组的长度$ $第二行输入n个整数 a_1,a_2,...a_n (1 ≤ a_i ≤ 10^9), 代表数组的元素$

输出描述

在一行上输出一个整数,表示最少需要多少次操作。

示例 1

输入

5
1 2 3 4 5

输出

3