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.
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 a single integer – the value of the only element left in the array if both players play optimally.
- ($$$15$$$ points) $$$N \leq 3$$$.
- ($$$25$$$ points) $$$1 \leq a_i \leq 2$$$.
- ($$$60$$$ points) No additional constraints.
32 1 4
2
41 1 1 2
1
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$$$.
