A. Максимизируйте оставшийся элемент
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, где $$$n$$$ — нечётное.

За одну операцию вы можете удалить из массива $$$a$$$ два соседних элемента, а затем объединить оставшиеся части массива. Например, из массива $$$[4,7,4,2,9]$$$ можно получить массивы $$$[4,2,9]$$$ и $$$[4,7,9]$$$ с помощью операций $$$[\underline{4,7}, 4,2,9] \to [4,2,9]$$$ и $$$[4,7,\underline{4,2},9] \to [4,7,9]$$$ соответственно. Однако мы не можем получить массив $$$[7,2,9]$$$, так как для этого нужно удалить несмежные элементы $$$[\underline{4},7,\underline{4},2,9]$$$.

Вы выполняете эту операцию несколько раз, пока в $$$a$$$ не останется ровно один элемент.

Найдите максимально возможное значение оставшегося элемента в $$$a$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 99$$$; $$$n$$$ — нечетное) — длина массива $$$a$$$.

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

Заметим, что сумма $$$n$$$ по всем наборам входных данных не ограничена.

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

Для каждого набора входных данных выведите одно целое число — максимально возможное значение оставшегося элемента в $$$a$$$.

Пример
Входные данные
4
1
6
3
1 3 2
5
4 7 4 2 9
7
3 1 4 1 5 9 2
Выходные данные
6
2
9
5
Примечание

В первом наборе входных данных массив $$$a$$$ равен $$$[6]$$$. Поскольку в нем только один элемент, никаких операций не требуется. Максимально возможное значение оставшегося элемента — $$$6$$$.

Во втором наборе входных данных массив $$$a$$$ равен $$$[1, 3, 2]$$$. Мы можем удалить первые два элемента $$$[\underline{1, 3}, 2] \to [2]$$$, или удалить последние два элемента $$$[1, \underline{3, 2}] \to [1]$$$. Таким образом, максимально возможное значение оставшегося элемента равно $$$2$$$.

В третьем наборе входных данных массив $$$a$$$ равен $$$[4, 7, 4, 2, 9]$$$. Один из способов максимизации оставшегося элемента — $$$[4, \underline{7, 4}, 2, 9] \to [\underline{4, 2}, 9] \to [9]$$$. Таким образом, максимально возможное значение оставшегося элемента равно $$$9$$$.

В четвертом наборе входных данных массив $$$a$$$ равен $$$[3, 1, 4, 1, 5, 9, 2]$$$. Можно показать, что максимально возможное значение оставшегося элемента равно $$$5$$$.