Problem E
Buying Votes

Karl-Gunnar is running for president in his programming club, and do not want to risk losing. He has managed to find out which candidate every member will vote for, and is planning to bribe some of them so that they vote for him instead.

Write a program that computes how many votes he needs to buy (i.e what members to bribe) so that he will win the election. To win the election, he needs strictly more votes than each of the other candidates.

Input

On the first line you can find a single integer – the number of candidates ($1 \le n \le 20$).

On the second line you can find $n$ integers, the number of votes each candidate would recieve without bribes. The first of these integers are Karl-Gunnar’s votes. All vote counts are between $0$ and $1000$.

Output

Your program should output a single line with an integer – the least number of votes that needs to be bought for Karl-Gunnar to recieve more votes than all the other candidates.

Grading

Your solution will be tested on a number of test groups. To get the points for a group, you must pass all the cases in the group.

Explanation of Sample 1

You can buy two votes from candidate 3, and three votes from candidate 4. You will then have 7 votes, and everyone else will have 5 votes.

4
2 5 7 8

5