C. Массив Чамо и Мокки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мокка любит массивы, поэтому перед отъездом Чамо подарил ей массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел.

Мокка не любит массивы, содержащие разные числа, поэтому Мокка решила использовать магию, чтобы изменить массив. Мокка может выполнить следующую трехэтапную операцию несколько (возможно, ноль) раз:

  1. Выбрать индексы $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq n$$$)
  2. Пусть $$$x$$$ — медиана$$$^\dagger$$$ подмассива $$$[a_l, a_{l+1},\ldots, a_r]$$$
  3. Сделать все значения $$$a_l, a_{l+1},\ldots, a_r$$$ равными $$$x$$$

Предположим, что изначально $$$a=[1,2,3,4,5]$$$:

  • Если Мокка на первой операции выберет $$$(l,r)=(3,4)$$$, то $$$x=3$$$, массив изменится на $$$a=[1,2,3,3,5]$$$.
  • Если Мокка на первой операции выберет $$$(l,r)=(1,3)$$$, то $$$x=2$$$, массив изменится на $$$a=[2,2,2,4,5]$$$.

Мокка будет выполнять операции до тех пор, пока все элементы массива не станут равными одному числу. Мокка хочет узнать, чему равняется максимально возможное значение этого числа.

$$$^\dagger$$$ Медиана в массиве $$$b$$$ длины $$$m$$$ — это элемент, занимающий позицию номер $$$\lfloor \frac{m+1}{2} \rfloor$$$ после сортировки элементов в неубывающем порядке. Например, медиана $$$[3,1,4,1,5]$$$ равна $$$3$$$, а медиана $$$[5,25,20,24]$$$ равна $$$20$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 10^5$$$) — длину массива $$$a$$$.

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

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

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

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

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

В первом наборе входных данных $$$a=[1,2]$$$. Мокка может выбрать только интервал $$$(l,r)=(1,2)$$$. Массив будет изменен на $$$a=[1,1]$$$. Поэтому ответом будет $$$1$$$.

Со вторым набором входных данных Мокка может выполнить следующие операции:

  • Выбрать интервал $$$(l,r)=(4,5)$$$, тогда $$$a=[1,2,3,4,4]$$$.
  • Выбрать интервал $$$(l,r)=(3,5)$$$, тогда $$$a=[1,2,4,4,4]$$$.
  • Выбрать интервал $$$(l,r)=(1,5)$$$, тогда $$$a=[4,4,4,4,4]$$$.

Все элементы массива равны $$$4$$$. Можно доказать, что максимальное значение конечного числа не может быть больше $$$4$$$.