← 返回题目列表

Codeforces · 574/A

A. 熊与选举

中文机器翻译题面 查看原题

利马克是一只渴望权力和崇拜的灰熊。他想在即将到来的选举中获胜并统治熊地。

有 n 个候选人,包括 Limak。我们知道有多少公民将投票给每位候选人。现在,第 i 位候选人将获得 ai 选票。利马克是一号候选人。为了赢得选举,他必须获得比任何其他候选人严格更多的选票。

胜利比其他一切都重要,所以 Limak 决定作弊。他会通过贿赂一些公民来窃取对手的选票。为了贿赂公民,利马克必须给他或她一颗糖果——公民是熊,熊就像糖果一样。利马克没有多少糖果和奇迹——他要贿赂多少公民?

输入

第一行包含单个整数 n (2 ≤ n ≤ 100) - 候选数。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 1000) - 每个候选人的票数。利马克是第一号候选人。

请注意,行贿后某些候选人的票数可能为零或可能大于 1000。

输出

打印 Limak 必须贿赂的最低公民数量,才能获得严格高于任何其他候选人的选票。

示例

输入 #1

5
5 1 11 2 8

输出 #1

4

输入 #2

4
1 8 8 8

输出 #2

6

输入 #3

2
7 6

输出 #3

0

注意

在第一个样本中,Limak 有 5 票。取得胜利的方法之一是贿赂 4 名想要投票给第三位候选人的公民。那么票数将为 9, 1, 7, 2, 8(利马克将有 9 票)。或者,Limak 可以只从第三个候选人那里窃取 3 票,从第二个候选人那里窃取 1 票,从而得到情况 9,0,8,2,8。

在第二个样本中,Limak 将从每位候选人那里窃取 2 票。情况将是7、6、6、6。

在第三个样本中,Limak 是胜利者,没有贿赂任何公民。