A. Игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два игрока играют в игру.

Изначально на доске написано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Каждый ход игрок выбирает одно число и стирает его. Так продолжается до тех пор, пока на доске не останется одно число, то есть всего игроки сделают $$$n - 1$$$ ход. Ходы игроки делают по очереди, начинает первый игрок.

Первый игрок хочет минимизировать оставшееся число, второй — максимизировать.

Вы хотите узнать, какое число останется на доске после $$$n - 1$$$ хода при оптимальной игре обоих.

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

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество чисел.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

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

Выведите одно число, которое останется на доске в результате игры.

Примеры
Входные данные
3
2 1 3
Выходные данные
2
Входные данные
3
2 2 2
Выходные данные
2
Примечание

В первом примере первый игрок убирает число $$$3$$$, второй убирает $$$1$$$, на доске остается число $$$2$$$.

Во втором примере на доске остается число $$$2$$$ независимо от действий игроков.