CF1975C.Chamo and Mocha's Array

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

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

对于每组测试数据，输出最终数组中所有元素相同的最大可能值。

在第一个测试用例中，$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$。

由 ChatGPT 4.1 翻译