1975C · Chamo and Mocha's Array

Problem: 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 Format: 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 Format: For each test case, output the maximum value of the number.

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