题目描述

Alice 和 Bob 想出了一个相当奇怪的游戏。他们有一个由整数 $a_1,a_2,\cdots,a_n$ 组成的数列。Alice 会选择一个确定的整数 $k$ 并告诉 Bob，接着：

• Bob 会选择两个整数 $i,j(1\leq i<j\leq n)$，然后在 $a_i,a_{i+1},\cdots,a_j$ 中得出最大的整数；
• 如果得出的整数严格大于 $k$，那么 Alice 获胜，否则 Bob 获胜。

请帮助 Alice 找到整数 $k$ 的最大值，使得她一定能够获胜。

输入格式

每个测试点由多组测试组成。输入的第一行是一个整数 $t$，表示测试组数。接下来是每组测试的数据：

每组测试的第一行是一个整数 $n$，表示数列的元素个数。

每组数据的第二行包括 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示数列中的元素。

输出格式

对于每组测试，输出一个整数，表示使 Alice 一定能够获胜的整数 $k$ 的最大值。

说明/提示

$1\leq i<j\leq n\leq5\times10^4,\sum n\leq5\times10^4,1\leq a_i\leq10^9$。

样例

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