思路：思维

记录 $sum = \sum\limits_{i=0}^{n-1} a_i$

如果 $sum \% n =0$ ，则所有数都可以修改为 $\frac{sum}{n}$ 。

否则，必然可以将 $n-1$ 个数通过操作修改为同样的数。 这是因为，假设使得 $a[1],a[2] \cdots,a[n-2], a[n - 1]$ 都变为 $1$ ，则 $a[i]$ 变为 $1$ 的增加或者减少，都由 $a[0]$ 来配对 。

现在问题转换为：

题目内容

小美有一个长度为 $n$ 的数组 $a$ ，但是小美很喜欢众数，所以他想改造这个数组，使得众数的出现次数尽可能多。

一次操作，小美可以选择两个下标 $i, j (1\leq i,j\leq n, i\neq j)$，使得 $a_i$ 减 $1$ ，$a_j$ 加 $1$ 。

现在小美想问你，使得众数出现次数最多的情况下，最少的操作次数是多少。

输入描述

第一行，一个正整数 $n(1\leq n\leq 10^5)$ ，表示数组 $a$ 的大小

第二行，$n$ 个正整数 $a_i(1\leq a_i\leq 10^9)$

输出描述

使得众数出现次数最多的情况下的最少操作次数。

样例

输入

3
1 2 3

输出

1

说明

$a_1$ 加 $1$ ，$a_3$ 减 $1$ ，一次操作得到 [2, 2, 2]