Description

Yuki and K are playing a game on a sequence of length $n$.

Yuki and K take turns to act. Yuki moves first. In each operation, the current player can split the sequence into two non-empty parts at a division point, and then the opponent in the game will delete one of the parts. The game continues with the remaining part.

Specifically, in the first round, Yuki splits and K deletes; in the second round, K splits and Yuki deletes; in the third round, Yuki splits and K deletes, and so on.

The game ends when only one number remains and no further operations can be performed. Yuki wants to maximize the last remaining number, while K wants to minimize it.

Assuming both players are infinitely smart, determine the final remaining number.

Input Format

The input contains $T$ test cases. The first line of input has an integer $T$.

For each test case, the first line contains a positive integer $n$.

The second line of each test case contains $n$ positive integers, where the $i$-th integer is $a_i$.

Output Format

For each test case, output an integer representing the final remaining number.

2
5
1 4 3 1 5
4
1 3 3 1

3
3

Hint

Explanation for the first sample: If Yuki chooses to split the sequence into the left 2 numbers and the right 3 numbers:

• If K deletes the right part, the remaining sequence is $1$ and $4$. Yuki can then ensure the final number is $4$ when K splits.
• If K deletes the left part, the remaining sequence is $3, 1, 5$. No matter how K splits next, Yuki can ensure the answer is no less than $3$.

Further analysis shows that the answer is $3$.

For all data, $1\le T\le 10$, $1\le n\le 10^5$, $1\le a_i\le 10^9$.