The century-long rivalry between Busy Beaver and Busy Revaeb rages on to this very day. This time, they decide to challenge each other in a two-player game.
There is a sequence of $N$ positive integers $a_1, \dots, a_N$. Busy Beaver and Busy Revaeb play a turn-based game as follows:
- Busy Beaver chooses two adjacent numbers in the sequence, erases them, and writes down the larger of the two erased numbers t- Busy Revaeb does the same, but writes down the smaller of the two erased numbers.
Busy Beaver goes first. The game ends when there is only one number $X$ remaining in the sequence. Busy Beaver wants to maximize $X$; Busy Revaeb wants to minimize it. Find the value of $X$ if both players play optimally.
Input
The first line contains $N$ ($1 \leq N \leq 2 \cdot 10^5$), the number of elements in the array.
The second line contains $N$ space-separated integers $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$).
Output
Output a single integer -- the value of the only element left in the array if both players play optimally.
Examples
Input 1
3 2 1 4
Output 1
2
Explanation 1
The last value cannot be $4$, because if Busy Beaver tries to keep $4$ by not choosing it on the first round, Busy Revaeb can take the $4$ the next round, leaving the last value $1$ or $2$. The last value also cannot be $1$ because Busy Revaeb could have taken the $1$ in round $1$, ensuring the last value is greater than $1$.
Busy Beaver can ensure the last value is at least $2$, and Busy Revaeb can ensure the last value is at most $2$. Thus, the last value will be $2$ under optimal play.
Input 1
4 1 1 1 2
Output 1
1
Explanation 2
The last value is either $1$ or $2$. If Busy Revaeb's strategy consists of taking $2$ as soon as possible, then he can guarantee that after his turn (turn $2$), the sequence contains only $1$s $-$ regardless of how Busy Beaver moves in turn $1$. Therefore, when both play optimally, the last value will be $1$.
Scoring
- ($15$ points) $N \leq 3$.
- ($25$ points) $1 \leq a_i \leq 2$.
- ($60$ points) No additional constraints.