Олимпиадный тренинг

Задача . A. Игра


Задача

Темы: сортировки *800

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

Изначально на доске написано \(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\), второй убирает \(1\), на доске остается число \(2\).

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


Примеры
№Входные данныеВыходные данные
1
3
2 1 3
2
2
3
2 2 2
2
Статистика успешных решений по компиляторам
 Кол-во
С++5