B. Min-Max Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 there.
  • 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.

Scoring
  • ($$$15$$$ points) $$$N \leq 3$$$.
  • ($$$25$$$ points) $$$1 \leq a_i \leq 2$$$.
  • ($$$60$$$ points) No additional constraints.
Examples
Input
3
2 1 4
Output
2
Input
4
1 1 1 2
Output
1
Note

Sample 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.

Sample 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$$$.