311384: CF1979A. Guess the Maximum

A. Guess the Maximumtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice and Bob came up with a rather strange game. They have an array of integers $a_1, a_2,\ldots, a_n$. Alice chooses a certain integer $k$ and tells it to Bob, then the following happens:

• Bob chooses two integers $i$ and $j$ ($1 \le i < j \le n$), and then finds the maximum among the integers $a_i, a_{i + 1},\ldots, a_j$;
• If the obtained maximum is strictly greater than $k$, Alice wins, otherwise Bob wins.

Help Alice find the maximum $k$ at which she is guaranteed to win.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 5 \cdot 10^4$) — the number of elements in the array.

The second line of each test case contains $n$ integers $a_1, a_2,\ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^4$.

Output

For each test case, output one integer — the maximum integer $k$ at which Alice is guaranteed to win.

ExampleInput

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

Output

3
1
0
15
9
2

Note

In the first test case, all possible subsegments that Bob can choose look as follows: $[2, 4], [2, 4, 1], [2, 4, 1, 7], [4, 1], [4, 1, 7], [1, 7]$. The maximums on the subsegments are respectively equal to $4, 4, 7, 4, 7, 7$. It can be shown that $3$ is the largest integer such that any of the maximums will be strictly greater than it.

In the third test case, the only segment that Bob can choose is $[1, 1]$. So the answer is $0$.

题目大意：
Alice和Bob玩一个游戏，有一个整数数组a1, a2, …, an。Alice选择一个整数k并告诉Bob，然后Bob做以下操作：
1. Bob选择两个整数i和j（1 ≤ i < j ≤ n），然后找出ai, ai+1, …, aj中的最大值；
2. 如果得到的最大值严格大于k，Alice赢，否则Bob赢。

帮助Alice找到确保她获胜的最大k值。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 5 × 10^4）——数组中元素的数量。
每个测试用例的第二行包含n个整数a1, a2, …, an（1 ≤ ai ≤ 10^9）——数组的元素。
保证所有测试用例的n之和不超过5 × 10^4。

输出数据格式：
对于每个测试用例，输出一个整数——确保Alice获胜的最大整数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

注意：
在第一个测试用例中，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。题目大意： Alice和Bob玩一个游戏，有一个整数数组a1, a2, …, an。Alice选择一个整数k并告诉Bob，然后Bob做以下操作： 1. Bob选择两个整数i和j（1 ≤ i < j ≤ n），然后找出ai, ai+1, …, aj中的最大值； 2. 如果得到的最大值严格大于k，Alice赢，否则Bob赢。 帮助Alice找到确保她获胜的最大k值。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 5 × 10^4）——数组中元素的数量。 每个测试用例的第二行包含n个整数a1, a2, …, an（1 ≤ ai ≤ 10^9）——数组的元素。 保证所有测试用例的n之和不超过5 × 10^4。 输出数据格式： 对于每个测试用例，输出一个整数——确保Alice获胜的最大整数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 注意： 在第一个测试用例中，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。