Вековое соперничество между Busy Beaver и Busy Revaeb продолжается по сей день. В этот раз они решили бросить друг другу вызов в игре для двух игроков.

Дана последовательность из $N$ положительных целых чисел $a_1, \dots, a_N$. Busy Beaver и Busy Revaeb играют в пошаговую игру следующим образом:

• Busy Beaver выбирает два соседних числа в последовательности, стирает их и записывает на их место большее из двух стертых чисел.
• Busy Revaeb делает то же самое, но записывает на их место меньшее из двух стертых чисел.

Busy Beaver ходит первым. Игра заканчивается, когда в последовательности остается только одно число $X$. Busy Beaver хочет максимизировать $X$, а Busy Revaeb хочет минимизировать его. Найдите значение $X$, если оба игрока играют оптимально.

Входные данные

Первая строка содержит $N$ ($1 \leq N \leq 2 \cdot 10^5$) — количество элементов в массиве.

Вторая строка содержит $N$ целых чисел $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$), разделенных пробелами.

Выходные данные

Выведите единственное целое число — значение последнего оставшегося элемента в массиве, если оба игрока играют оптимально.

Оценивание

• ($15$ баллов) $N \leq 3$.
• ($25$ баллов) $1 \le a_i \le 2$.
• ($60$ баллов) Без дополнительных ограничений.

Примеры

Входные данные 1

3
2 1 4

Выходные данные 1

2

Примечание

Последнее значение не может быть $4$, потому что если Busy Beaver попытается сохранить $4$, не выбирая его в первом раунде, Busy Revaeb может забрать $4$ в следующем раунде, оставив в качестве последнего значения $1$ или $2$. Последнее значение также не может быть $1$, так как Busy Revaeb мог забрать $1$ в первом раунде, гарантируя, что последнее значение будет больше $1$.

Busy Beaver может гарантировать, что последнее значение будет не меньше $2$, а Busy Revaeb может гарантировать, что оно будет не больше $2$. Таким образом, при оптимальной игре последнее значение будет равно $2$.

Входные данные 2

4
1 1 1 2

Выходные данные 2

1

Примечание

Последнее значение равно либо $1$, либо $2$. Если стратегия Busy Revaeb заключается в том, чтобы забрать $2$ как можно скорее, то он может гарантировать, что после его хода (второй ход в игре) в последовательности останутся только $1$ — независимо от того, как Busy Beaver сходит в первом раунде. Следовательно, при оптимальной игре обоих игроков, последнее значение будет равно $1$.