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

Алиса и Боб придумали довольно странную игру. У них есть массив целых чисел $$$a_1, a_2,\ldots, a_n$$$. Алиса выбирает некоторое целое число $$$k$$$ и сообщает его Бобу, после чего происходит следующее:

  • Боб выбирает два целых числа $$$i$$$ и $$$j$$$ ($$$1 \le i < j \le n$$$), а затем ищет максимум среди чисел $$$a_i, a_{i + 1},\ldots, a_j$$$;
  • Если полученный максимум строго больше $$$k$$$, то побеждает Алиса, иначе Боб.

Помогите Алисе узнать максимальное $$$k$$$, при котором она гарантированно побеждает.

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

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

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

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

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

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

Для каждого набора входных данных выведите одно целое число — максимальное целое число $$$k$$$, при котором Алиса гарантированно побеждает.

Пример
Входные данные
6
4
2 4 1 7
5
1 2 3 4 5
2
1 1
3
37 8 16
5
10 10 10 10 9
10
3 12 9 5 2 3 2 9 8 2
Выходные данные
3
1
0
15
9
2
Примечание

В первом наборе входных данных всевозможные подотрезки, которые может выбрать Боб, выглядят следующим образом: $$$[2, 4], [2, 4, 1], [2, 4, 1, 7], [4, 1], [4, 1, 7], [1, 7]$$$. Максимумы на подотрезках соответственно равны $$$4, 4, 7, 4, 7, 7$$$. Можно показать, что $$$3$$$ является наибольшим целым числом, таким что любой из максимумов будет строго больше него.

В третьем наборе входных данных единственным отрезком, который может выбрать Боб, является $$$[1, 1]$$$. Поэтому ответ равен $$$0$$$.