问题 A: 选举

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：207 通过：105

返回比赛提交提交记录

文海小学501班即将进行班长选举，有n个候选人，期中包括kk同学。我们知道有多少位同学参与投票投票给每个候选人。现在第i个候选人将得到ai票。kk同学的候选人编号为1。为了在选举中获胜，他必须获得比其他任何候选人都多的选票。

胜利比什么都重要，所以kk决定使出杀招。作为学霸的他，决定通过帮助同学们学习，来提高他的胜选率。kk在竞选演讲中承诺将为每一位需要补课的同学答疑。给一位同学补课，他将获得这位同学的选票，为了能赢得选取，KK至少需要给多少位同学补课呢？

第一行包含单个整数n (2<=n<=100）- 候选人人数。

第二行包含n空格分隔的整数a1,a2·····an( 1<=ai<=1000） - 每个候选人的票数。KK是候选人编号1

请注意，帮忙补课的人数可能为零，也可能大于1000

输入kk必须帮忙补课的最低同学人数，才能获得比其他任何候选人都多的选票。

Examples

Input

5
5 1 11 2 8

Output

Input

4
1 8 8 8

Output

Input

2
7 6

Output

注意

在第一个样本中，kk有5票。取得胜利的方法之一是给4名想要投票给第三位候选人的同学补课。那么票数将是9，1，7，2，8（kk将有9票）。或者，kk只能从第三名候选人那里窃取 3 票，从第二名候选人那里窃取 1 票，以获得情况 9，0，8，2，8。
在第二个样本中，kk将从每个候选人那里窃取 2 票。情况将是7，6，6，6。
在第三个样本中，kk是没有给任何同学补课的赢家。

5
5 1 11 2 8

574A 1200 greedy implementation 思维

问题 A: 选举

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签

问题 A: 选举

题目描述

输入格式

输出格式

输入样例 复制

输出样例 复制

分类标签

输入样例复制

输出样例复制