← 返回题目列表

Codeforces · 1979/A

A. 猜猜最大值

中文机器翻译题面 查看原题

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$$$。