Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Bear and Elections

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLimak 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 *a*_{i} 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?

Input

The first line contains single integer *n* (2 ≤ *n* ≤ 100) - number of candidates.

The second line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 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.

Output

Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.

Examples

Input

5

5 1 11 2 8

Output

4

Input

4

1 8 8 8

Output

6

Input

2

7 6

Output

0

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 00:05:31 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|