该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

在比奇堡小镇上，正在举行着盛大的镇长选举。镇上有 $n$ 位候选人，每位候选人的支持者数量（即他们当前的选票）已经确定。对于每一位候选人，第 $i$ 位候选人在预投票时拥有 $a_i$ 张选票（“不出意外”的情况下正式投票的票数不会改变）。

不出意外马上就要出意外了，当痞老板发现如果自己当上镇长就可以通过法案让所有比奇堡的居民都来自己的海之霸餐厅吃海霸棒，他对于当镇长的野心突然膨胀了起来。

但目前他的选票并不是最多的，甚至可能是最少的。他的妻子凯伦告诉痞老板他可以通过一些不太光彩的手段，来实现赢得选举的目标。

最终痞老板决定通过贿赂的方式来增加他的选票。每贿赂一位居民，痞老板只需要给他一枚金币，这样他就能让这位居民倒戈（不再按照预投票时的情况进行投票）。因此，痞老板想方设法要通过贿赂足够多的居民来超过其他候选人的票数，从而赢得选举。

现在，痞老板想要请你帮他正在计算他至少需要多少枚金币，才能确保他的选票数量超过其他所有候选人，成为选举的赢家。

输入格式

第一行一个正整数 $n$

第二行 $n$ 个整数表示预投票时每位候选人的支持者数量，其中第 $1$ 项是痞老板预投票时支持者的数量。

输出格式

痞老板至少需要多少枚金币，才能成功当选

5
5 1 11 2 8

4

样例说明：

第 $1$ 次，贿赂 $3$ 号候选人的支持者，票数变成 6 1 10 2 8

第 $2$ 次，贿赂 $3$ 号候选人的支持者，票数变成 7 1 9 2 8

第 $3$ 次，贿赂 $3$ 号候选人的支持者，票数变成 8 1 8 2 8

第 $4$ 次，贿赂 $3$ 号候选人的支持者，票数变成 9 1 7 2 8

此时痞老板的票数最多，当选镇长，共花费 $4$ 枚金币，并且可以证明是最优的方法之一。

4
1 8 8 8

6

数据范围

测试点 $1\sim 6$ ：满足 $2\le n \le 2\times 10^3$；$0\le a_i \le 10^3$

测试点 $7\sim 14$ ：满足 $2\le n \le 2\times 10^5$；$0\le a_i \le 10^5$

测试点 $15\sim 20$ ：满足 $2\le n \le 2\times 10^5$；$0\le a_i \le 10^{18}$；保证票数最多的人 $i$ 与票数最少的人 $j$ 之间满足 $a_i - a_j \le 10^5$