You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $n$ 盒糖，第 $i$ 盒糖中有 $a_i$ 颗糖。你有 $n$ 个朋友，你想给每个朋友发一盒糖。 但是每盒糖的数量可能不一样，所以你想要吃掉一些糖，使得每盒糖中糖数相等。 注意：你可以在不同的盒子中吃掉不同数量的糖（可以不吃），但不能向任何盒子中加糖。 问你最少吃掉多少颗糖，才能完成目标。

输入格式

第一行包含一个整数 $n$ 代表您拥有的盒子数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 代表每个盒子中糖果的数量。

输出格式

对于每个测试用例，打印一个整数，表示要满足要求所需的最少糖果数量。

样例1

input

5
1 2 3 4 5

output

10

样例2

input

6
1000 1000 5 1000 1000 1000

output

4975

样例解释

在第一个测试案例中，你可以吃掉第二个盒子中的 $1$ 颗糖果，第三个盒子中的 $2$ 颗糖果，第四个盒子中的 $3$ 颗糖果，第五个盒子中的 $4$ 颗糖果。现在这些盒子里有 $[1,1,1,1,1]$ 粒糖果，而你一共吃了 $0+1+2+3+4=10$ 粒糖果，所以答案是 $10$ 。

限制与约定

对于 $50\%$ 的数据，$1 \le n \le 100$ , $1 \le a_i \le 1000$

对于 $100\%$ 的数据，$1 \le n \le 10^5$ , $1 \le a_i \le 10^6$ 。

• 时间限制: $1 s$
• 空间限制: $256 MB$