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.

题目描述

小 Y 是一个邪恶的资本家，手下有 $n$ 个被剥削的工人，编号从 $1$ 到 $n$。

编号为 $i$ 的工人目前的工资是 $a_i$ 元。在小 Y 的严格监管下，工人们不能互相告知自己的工资。小 Y 以为好日子会一直这样持续下去，但是工人们越来越感觉到不平等，发现自己被剥削，于是他们决定罢工抗议小 Y ！

没有工人的劳动，就没有小 Y 奢侈的生活。于是小 Y 决定以适当的方式提高他们的工资，来让他们停止抗议。一开始，每个工人都是不满意的。小 Y 需要组织几次聊天，每次聊天只会有两个工人参与。 最终的目的是让每个工人都满意，或者只有一个人不满意——此时，将没有人愿意和他一起抗议小 Y 。

为了组织一次聊天，小 Y 需要选出两个当前不满意的工人$x,y$，然后临时允许他们讨论自己的工资：

• 如果$a_x=a_y$（即工资相同），这两个工人都会觉得自己没有受到不公平的待遇，都会改为满意。

• 如果$a_x>a_y$，那么工人$x$会感到满意。但是工人$y$会意识到自己受到了不公平的待遇，所以小 Y 需要把他的工资提高到$a_x$（即小 Y 要多付给他$a_x-a_y$元，然后把$a_y$ 改为 $a_x$），并且此时工人 $y$ 仍然不满意。

• 类似地，如果 $a_y>a_x$ 那么工人 $y$ 会感到满意。但是小 Y 必须付给工人 $x$ $a_y-a_x$ 元，然后把 $a_x$ 改为 $a_y$，并且工人 $x$ 仍然不满意。

但是作为一个邪恶的资本家，小 Y 想知道自己最少需要付给他们多少钱才能达到目标，于是请来精通会计的你来帮他计算一下。

输入格式

从 money.in 文件读入数据。

第一行包含一个整数 $n$，表示员工的个数。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ ，代表每个工人初始的工资。

输出格式

输出到 money.out 文件。

一个整数，表示所需付出的最少钱数。

样例 1

4
100 101 1 101

1

你可以先让工人1和工人2对话，工人2会满意，你需要付给工人1元钱，$a_1$ 变成 $101$。

然后你可以让工人1和工人4对话，因为他们的工资一样，所以他们都会满意。

这时只有工人3不满意，你的目的已经达到了。

样例 2

点击链接 ex_money2.in 和 ex_money2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点， 保证 $1\le n\le 2\times 10^5, 1\le a_i\le 10^9$