← 返回题目列表

Codeforces · 1975/C

C. 查莫和摩卡的阵列

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

Mocha 喜欢数组,所以在她出发之前,Chamo 送给她一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ 作为礼物。

Mocha 不喜欢包含不同数字的数组,因此 Mocha 决定使用魔法来更改数组。 Mocha 可以执行以下三步操作几次(可能是零次):

1. 选择索引 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l < r \leq n$$$)
2. 设$$$x$$$为子数组$$$[a_l, a_{l+1},\ldots, a_r]$$$的中位数$$$^\dagger$$$
3. 将所有值 $$$a_l, a_{l+1},\ldots, a_r$$$ 设置为 $$$x$$$

假设 $$$a=[1,2,3,4,5]$$$ 最初:

- 如果Mocha在第一次操作中选择$$$(l,r)=(3,4)$$$,则$$$x=3$$$,数组将变为$$$a=[1,2,3,3,5]$$$。
- 如果Mocha在第一次操作中选择$$$(l,r)=(1,3)$$$,则$$$x=2$$$,数组将变为$$$a=[2,2,2,4,5]$$$。

Mocha 将执行该操作,直到数组仅包含相同的数字。 Mocha 想知道这个数字的最大可能值是多少。

$$$^\dagger$$$ 长度为 $$$m$$$ 的数组 $$$b$$$ 中的中位数是按非降序对元素进行排序后占据位置号 $$$\lfloor \frac{m+1}{2} \rfloor$$$ 的元素。例如,$$$[3,1,4,1,5]$$$ 的中位数为 $$$3$$$,$$$[5,25,20,24]$$$ 的中位数为 $$$20$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出数字的最大值。

示例

输入 #1

2
2
1 2
5
1 2 3 4 5

输出 #1

1
4

注意

在第一个测试用例中,$$$a=[1,2]$$$。 Mocha只能选择区间$$$(l,r)=(1,2)$$$。该数组将更改为 $$$a=[1,1]$$$。因此,答案是$$$1$$$。

在第二个测试用例中,Mocha可以执行以下操作:

- 选择区间$$$(l,r)=(4,5)$$$,然后$$$a=[1,2,3,4,4]$$$。
- 选择区间 $$$(l,r)=(3,5)$$$,然后 $$$a=[1,2,4,4,4]$$$。
- 选择区间 $$$(l,r)=(1,5)$$$,然后 $$$a=[4,4,4,4,4]$$$。

该数组仅包含相同的数字,即 $$$4$$$。可以证明最终数的最大值不能大于$$$4$$$。