After seeing the astronomically large bill of the restraunt, You have come to your senses and decided to select which dish to buy using the algorithm taught to you by Jatin sir.
You first place the n number of dishes in a line. Each dish i has a price ai and all the prices are distinct. You repeat the following unless there’s one or no dish left. Take the most expensive dish from the line and the dish just left of it and remove both of them(if there's no dish to the left of it then only the most expensive dish is removed). Finally if there's one dish left then you decide to buy the dish, else you thank the fate for not allowing you to spend your money.
Write a program that given the arrangement and prices of dishes, print the price of the dish you are going to buy. If you don't buy any dish then print 1.
Input:
First line contains the integer n , the number of dishes. Next line contains n space separated integers where the ith integer is ai, the price of dish i
Output:
Print the answer as defined in the question.
Constraints:
1≤n≤105
1≤ai≤109
The arrangement with the prices is [3,2,1,5,4], the most expensive dish has cost 5 and the dish left of it has cost 1. After removing them we have the array [3,2,4]. Now the most expensive dish has cost 4 and the dish left of it has cost 2. After removing them we have the array [3]. Now since there's one dish left we finally buy this dish and hence 3 is the answer.