Power of the Champion

On Eid-Day the king of Mueawin announced an interesting game for the people of his country. The rule of the game is very simple. n player participates in this game and every player has an initial power. In every round of this game, among remaining players, the most powerful player will fight against the lowest powerful player and the second most powerful player against the second-lowest powerful player and the third most powerful player against third-lowest powerful player and so on. If the number of remaining players is odd than a player (middle positioned player after sorting) will advance to the next round without fight. All the time the most powerful player will advance to the next round and his opponent goes out of the game. If the two player (fighting against each other) power is the same then one of them will advance to the next level but his power will be decreased by 1 unit.

An intelligent man named Pasu informed the king that he can say the value of the power of champion of the game by seeing the initial power of all players. The king will give a prize to Pasu if he informs correctly otherwise he will be punished.

Can you help Pasu to ensure that he is right? You have to print the value of the power of the champion of the game.

Input

The first line will contain a positive integer n (1 ≤ n ≤ 105), the number of player in the game.
The next line will contain n space-separated integer a1, a2, a3 ... an where ai(1 ≤ ai ≤1015) is the power of the ith player.

Output

Print the value of the power of the champion. Print 0 if the answer is negative.

Samples

Input	Output
4 8 8 8 8	6

Input	Output
3 8 8 8	8