P13309 演劇

[演劇](https://music.163.com/#/song?id=2156223367)。 > 間違ったまま　生きてきたんだ > > 今更首輪を外されたって > > 一体何処へ行けばいいの

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.

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

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

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$. | Test | $n\le$ | | :-----------: | :-----------: | | $1$ | $5$ | | $2\sim 3$ | $100$ | | $4\sim 6$ | $1000$ | | $7\sim 10$ | $10^5$ | For all data, $1\le T\le 10$, $1\le n\le 10^5$, $1\le a_i\le 10^9$.