F. Fierce election
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the quest for adoration and ego enhancement, the gods of Olympus organize an election on Earth every 100 years to determine the most adored god by humans. In this edition, $$$m$$$ deities, including Byakronos, Marceloki, and Zeos, the favorites, are competing for the title. Only a few randomly selected individuals are invited to vote.

The prophet Kobus, a fervent follower of Zeos, is determined to secure his victory. She possesses privileged knowledge about the voters and knows exactly how many votes each god has received up to the moment. For the $$$i$$$-th god, she has information that they have received the partial quantity of votes $$$a_i$$$.

However, Kobus needs your help to determine the minimum quantity $$$t$$$ of votes she must purchase to ensure Zeos' victory. In other words, Zeos must have more votes than any other deity in the competition. It is important to note that Zeos is the first god on the list provided by Kobus and that when she buys a vote, it is taken from another god and transferred to Zeos.

Input

The first line contains an integer $$$m$$$ ($$$3 \leq m \leq 2 \cdot 10^5$$$) - the number of gods competing for the title.

The second line provides $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \leq a_i \leq 10^9$$$) - where $$$a_i$$$ indicates how many humans voted for the $$$i$$$-th god.

Output

The output should be a single integer $$$t$$$ indicating the minimum number of votes that Kobus needs to buy.

Examples
Input
3
1 1 7
Output
4
Input
3
1 2 6
Output
3
Input
6
2 4 2 5 6 5
Output
4
Note

In the first example, it can be proven that $$$3$$$ votes are not enough since, regardless of how Kobus buys them, the third candidate would still have more votes than Zeos.

On the other hand, if she buys $$$4$$$ votes from the third candidate for Zeos, he would have $$$5$$$ voters (while the third candidate has only $$$3$$$).