B. Черепаха и Свинка играют в игру 2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Черепаха и Свинка играют в игру на последовательности. Им дана последовательность $$$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$$$ в конце, если оба игрока играют оптимально.

Вы можете обратиться к примечаниям для дальнейшего разъяснения.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Описание наборов следует далее.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — длина последовательности.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — элементы последовательности $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$10^5$$$.

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

Для каждого набора выведите одно целое число — значение $$$a_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
Примечание

В первом наборе изначально $$$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$$$ в конце.