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