Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.
There are n candidates, including Limak. We know how many citizens are going to vote for each candidate. Now i-th candidate would get ai votes. Limak is candidate number 1. To win in elections, he must get strictly more votes than any other candidate.
Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?
The first line contains single integer n (2 ≤ n ≤ 100) - number of candidates.
The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1000) - number of votes for each candidate. Limak is candidate number 1.
Note that after bribing number of votes for some candidate might be zero or might be greater than 1000.
Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.
5 5 1 11 2 8
4
4 1 8 8 8
6
2 7 6
0
In the first sample Limak has 5 votes. One of the ways to achieve victory is to bribe 4 citizens who want to vote for the third candidate. Then numbers of votes would be 9, 1, 7, 2, 8 (Limak would have 9 votes). Alternatively, Limak could steal only 3 votes from the third candidate and 1 vote from the second candidate to get situation 9, 0, 8, 2, 8.
In the second sample Limak will steal 2 votes from each candidate. Situation will be 7, 6, 6, 6.
In the third sample Limak is a winner without bribing any citizen.
题目大意：Limak要参加选举，共有n个候选人，他是第一个，给出他们获得的选票，Limak可以花费一个糖果从某个候选人那里拉到一个人，问至少要多少个糖果才能使Limak的票数严格大于其他人。
有线性算法，但我太懒了，没去想。用一个堆维护其他候选人的票数，每次从选票最多的那个人里拉一个人，知道选票最多的人的票数小于Limak的票数。
代码在此。
评论 (0)
