time limit per test
1 second
memory limit per test
256 megabytes
Alice and Bob came up with a rather strange game. They have an array of integers a1,a2,…,ana1,a2,…,an. Alice chooses a certain integer kk and tells it to Bob, then the following happens:
- Bob chooses two integers ii and jj (1≤i<j≤n1≤i<j≤n), and then finds the maximum among the integers ai,ai+1,…,ajai,ai+1,…,aj;
- If the obtained maximum is strictly greater than kk, Alice wins, otherwise Bob wins.
Help Alice find the maximum kk at which she is guaranteed to win.
Input
Each test consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer nn (2≤n≤5⋅1042≤n≤5⋅104) — the number of elements in the array.
The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the elements of the array.
It is guaranteed that the sum of nn over all test cases does not exceed 5⋅1045⋅104.
Output
For each test case, output one integer — the maximum integer kk at which Alice is guaranteed to win.
Example
Input
Copy
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
Copy
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][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,74,4,7,4,7,7. It can be shown that 33 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][1,1]. So the answer is 00.
解题说明：水题，遍历，每次取前后两个数字，然后求出所有配对中的最小值，再用这个值减去1即可。
#include<stdio.h>
int main()
{int t;scanf("%d", &t);for (int q = 0; q < t; q++){int l;scanf("%d", &l);int num[50005];for (int i = 0; i < l; i++){scanf("%d", &num[i]);}int min = 1000000000;for (int i = 0; i < l - 1; i++){if (num[i] < min && num[i + 1] < min){if (num[i] < num[i + 1]){min = num[i + 1];}else{min = num[i];}}}printf("%d\n", min - 1);}return 0;
}