Trwająca od stuleci rywalizacja między Busy Beaverem a Busy Revaebem trwa do dziś. Tym razem postanowili zmierzyć się w grze dla dwóch graczy.
Dany jest ciąg $N$ dodatnich liczb całkowitych $a_1, \dots, a_N$. Busy Beaver i Busy Revaeb grają w grę turową według następujących zasad:
- Busy Beaver wybiera dwie sąsiednie liczby w ciągu, usuwa je i zapisuje w ich miejsce większą z usuniętych liczb.
- Busy Revaeb robi to samo, ale zapisuje w ich miejsce mniejszą z usuniętych liczb.
Busy Beaver wykonuje ruch jako pierwszy. Gra kończy się, gdy w ciągu pozostanie tylko jedna liczba $X$. Busy Beaver chce zmaksymalizować $X$, natomiast Busy Revaeb chce go zminimalizować. Znajdź wartość $X$, jeśli obaj gracze grają optymalnie.
Wejście
Pierwsza linia zawiera $N$ ($1 \leq N \leq 2 \cdot 10^5$), liczbę elementów w tablicy.
Druga linia zawiera $N$ liczb całkowitych $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$) oddzielonych spacjami.
Wyjście
Wypisz jedną liczbę całkowitą — wartość jedynego elementu pozostałego w tablicy, jeśli obaj gracze grają optymalnie.
Punktacja
- ($15$ punktów) $N \leq 3$.
- ($25$ punktów) $1 \le a_i \le 2$.
- ($60$ punktów) Brak dodatkowych ograniczeń.
Przykład
Wejście 1
3 2 1 4
Wyjście 1
2
Uwagi
Dla przykładu 1: Ostatnia wartość nie może wynosić $4$, ponieważ jeśli Busy Beaver spróbuje zachować $4$, nie wybierając go w pierwszej rundzie, Busy Revaeb może wybrać $4$ w następnej rundzie, pozostawiając jako ostatnią wartość $1$ lub $2$. Ostatnia wartość nie może również wynosić $1$, ponieważ Busy Revaeb mógłby wybrać $1$ w pierwszej rundzie, zapewniając, że ostatnia wartość będzie większa niż $1$. Busy Beaver może zapewnić, że ostatnia wartość wyniesie co najmniej $2$, a Busy Revaeb może zapewnić, że ostatnia wartość wyniesie co najwyżej $2$. Zatem przy optymalnej grze ostatnia wartość wyniesie $2$.
Wejście 2
4 1 1 1 2
Wyjście 2
1
Uwagi
Dla przykładu 2: Ostatnia wartość wynosi $1$ lub $2$. Jeśli strategia Busy Revaeba polega na wybraniu $2$ tak szybko, jak to możliwe, może on zagwarantować, że po jego ruchu (ruch $2$) ciąg będzie zawierał tylko $1$ — niezależnie od tego, jak Busy Beaver wykona ruch w pierwszej turze. Dlatego przy optymalnej grze obu stron ostatnia wartość wyniesie $1$.