Черепаха и Свинка играют в игру на последовательности. Им дана последовательность \(a_1, a_2, \ldots, a_n\). Черепаха ходит первой. Животные ходят по очереди(т.е. Черепаха делает первый ход, Свинка делает второй, Черепаха делает третий и т.д.).
Игра проходит следующим образом:
- Пусть текущая длина последовательности равна \(m\). Если \(m = 1\), игра заканчивается.
- Если игра не закончилась и ходит Черепаха, то Черепаха должна выбрать целое число \(i\) такое, что \(1 \le i \le m - 1\), сделать \(a_i\) равным \(\max(a_i, a_{i + 1})\) и удалить \(a_{i + 1}\).
- Если игра не закончилась и ходит Свинка, то Свинка должна выбрать целое число \(i\) такое, что \(1 \le i \le m - 1\), сделать \(a_i\) равным \(\min(a_i, a_{i + 1})\) и удалить \(a_{i + 1}\).
Черепаха хочет максимизировать значение \(a_1\) в конце, в то время как Свинка хочет минимизировать значение \(a_1\) в конце. Найдите значение \(a_1\) в конце, если оба игрока играют оптимально.
Вы можете обратиться к примечаниям для дальнейшего разъяснения.
Выходные данные
Для каждого набора выведите одно целое число — значение \(a_1\) в конце, если оба игрока играют оптимально.
Примечание
В первом наборе изначально \(a = [1, 2]\). Черепаха может выбрать только \(i = 1\). Затем она сделает \(a_1\) равным \(\max(a_1, a_2) = 2\) и удалит \(a_2\). Последовательность \(a\) становится \([2]\). Затем длина последовательности становится \(1\), и игра закончится. Значение \(a_1\) равно \(2\), поэтому вы должны вывести \(2\).
Во втором наборе один из возможных процессов игры выглядит следующим образом:
- Изначально \(a = [1, 1, 2]\).
- Черепаха может выбрать \(i = 2\). Затем она сделает \(a_2\) равным \(\max(a_2, a_3) = 2\) и удалит \(a_3\). Последовательность \(a\) станет \([1, 2]\).
- Свинка может выбрать \(i = 1\). Затем она сделает \(a_1\) равным \(\min(a_1, a_2) = 1\) и удалит \(a_2\). Последовательность \(a\) станет \([1]\).
- Длина последовательности становится \(1\), так что игра закончится. Значение \(a_1\) будет \(1\) в конце.
В четвертом наборе один из возможных процессов игры выглядит следующим образом:
- Изначально \(a = [3, 1, 2, 2, 3]\).
- Черепаха может выбрать \(i = 4\). Затем она сделает \(a_4\) равным \(\max(a_4, a_5) = 3\) и удалит \(a_5\). Последовательность \(a\) станет \([3, 1, 2, 3]\).
- Свинка может выбрать \(i = 3\). Затем она сделает \(a_3\) равным \(\min(a_3, a_4) = 2\) и удалит \(a_4\). Последовательность \(a\) станет \([3, 1, 2]\).
- Черепаха может выбрать \(i = 2\). Затем она сделает \(a_2\) равным \(\max(a_2, a_3) = 2\) и удалит \(a_3\). Последовательность \(a\) станет \([3, 2]\).
- Свинка может выбрать \(i = 1\). Затем она сделает \(a_1\) равным \(\min(a_1, a_2) = 2\) и удалит \(a_2\). Последовательность \(a\) станет \([2]\).
- Длина последовательности становится \(1\), так что игра закончится. Значение \(a_1\) будет \(2\) в конце.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 2
3
1 1 2
3
1 2 3
5
3 1 2 2 3
10
10 2 5 2 7 9 2 5 10 7
|
2
1
2
2
7
|