Два игрока играют в игру.
Изначально на доске написано \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Каждый ход игрок выбирает одно число и стирает его. Так продолжается до тех пор, пока на доске не останется одно число, то есть всего игроки сделают \(n - 1\) ход. Ходы игроки делают по очереди, начинает первый игрок.
Первый игрок хочет минимизировать оставшееся число, второй — максимизировать.
Вы хотите узнать, какое число останется на доске после \(n - 1\) хода при оптимальной игре обоих.
Выходные данные
Выведите одно число, которое останется на доске в результате игры.
Примечание
В первом примере первый игрок убирает число \(3\), второй убирает \(1\), на доске остается число \(2\).
Во втором примере на доске остается число \(2\) независимо от действий игроков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1 3
|
2
|
|
2
|
3
2 2 2
|
2
|