codeforces#P1979A. Guess the Maximum
Guess the Maximum
Description
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.
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$.
For each test case, output one integer — the maximum integer $k$ at which Alice 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.
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
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$.