Alice 和 Bob 想出了一个相当奇怪的游戏。它们有一个整数数组 $$$a_1, a_2,\ldots, a_n$$$。 Alice 选择某个整数 $$$k$$$ 并将其告诉 Bob,然后会发生以下情况:
- Bob 选择两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < j \le n$$$),然后在整数 $$$a_i, a_{i + 1},\ldots, a_j$$$ 中找到最大值;
- 如果获得的最大值严格大于 $$$k$$$,则 Alice 获胜,否则 Bob 获胜。
帮助 Alice 找到保证她获胜的最大 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - Alice 保证获胜的最大整数 $$$k$$$。
示例
输入 #1
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
输出 #1
3 1 0 15 9 2
注意
在第一个测试用例中,Bob 可以选择的所有可能的子段如下所示:$$$[2, 4], [2, 4, 1], [2, 4, 1, 7], [4, 1], [4, 1, 7], [1, 7]$$$。子段上的最大值分别等于$$$4,4,7,4,7,7$$$。可以证明 $$$3$$$ 是最大整数,任何最大值都将严格大于它。
在第三个测试用例中,Bob 唯一可以选择的段是 $$$[1, 1]$$$。所以答案是$$$0$$$。