311366: CF1975C. Chamo and Mocha's Array

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

C. Chamo and Mocha's Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Mocha likes arrays, so before her departure, Chamo gave her an array $a$ consisting of $n$ positive integers as a gift.

Mocha doesn't like arrays containing different numbers, so Mocha decides to use magic to change the array. Mocha can perform the following three-step operation some (possibly, zero) times:

  1. Choose indices $l$ and $r$ ($1 \leq l < r \leq n$)
  2. Let $x$ be the median$^\dagger$ of the subarray $[a_l, a_{l+1},\ldots, a_r]$
  3. Set all values $a_l, a_{l+1},\ldots, a_r$ to $x$

Suppose $a=[1,2,3,4,5]$ initially:

  • If Mocha chooses $(l,r)=(3,4)$ in the first operation, then $x=3$, the array will be changed into $a=[1,2,3,3,5]$.
  • If Mocha chooses $(l,r)=(1,3)$ in the first operation, then $x=2$, the array will be changed into $a=[2,2,2,4,5]$.

Mocha will perform the operation until the array contains only the same number. Mocha wants to know what is the maximum possible value of this number.

$^\dagger$ The median in an array $b$ of length $m$ is an element that occupies position number $\lfloor \frac{m+1}{2} \rfloor$ after we sort the elements in non-decreasing order. For example, the median of $[3,1,4,1,5]$ is $3$ and the median of $[5,25,20,24]$ is $20$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 500$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\leq n\leq 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output the maximum value of the number.

ExampleInput
2
2
1 2
5
1 2 3 4 5
Output
1
4
Note

In the first test case, $a=[1,2]$. Mocha can only choose the interval $(l,r)=(1,2)$. The array will be changed to $a=[1,1]$. Therefore, the answer is $1$.

In the second test case, Mocha can perform the following operations:

  • Choose the interval $(l,r)=(4,5)$, then $a=[1,2,3,4,4]$.
  • Choose the interval $(l,r)=(3,5)$, then $a=[1,2,4,4,4]$.
  • Choose the interval $(l,r)=(1,5)$, then $a=[4,4,4,4,4]$.

The array contains only the same number, which is $4$. It can be proven that the maximum value of the final number cannot be greater than $4$.

Output

题目大意：
Mocha喜欢数组，所以Chamo在她离开前给了她一个由n个正整数组成的数组a作为礼物。Mocha不喜欢包含不同数字的数组，所以她决定使用魔法来改变数组。Mocha可以执行以下三步操作若干次（可能为零次）：
1. 选择索引l和r（1≤l 2. 设x为子数组[a_l, a_{l+1},…, a_r]的中位数
3. 将所有值a_l, a_{l+1},…, 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想要知道这个数字的最大可能值是多少。

输入输出数据格式：
输入：
- 每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤500）。
- 每个测试用例的第一行包含一个整数n（2≤n≤10^5）——数组a的长度。
- 每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——数组a的元素。
- 保证所有测试用例的n之和不超过10^5。

输出：
- 对于每个测试用例，输出数字的最大可能值。

示例：
输入：
2
2
1 2
5
1 2 3 4 5

输出：
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。题目大意： Mocha喜欢数组，所以Chamo在她离开前给了她一个由n个正整数组成的数组a作为礼物。Mocha不喜欢包含不同数字的数组，所以她决定使用魔法来改变数组。Mocha可以执行以下三步操作若干次（可能为零次）： 1. 选择索引l和r（1≤l

Source/Category

加入题单

上一题 下一题 算法标签：