P17335 再生

[再生](https://music.163.com/#/song?id=1988508926)。 >浅い浅い夢なら全て許せたのに > >さらりさらり落ちてく何もかもが全て

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 turn, the current player can split the sequence into two non-empty parts at a division point, then **the player in this turn** deletes one of the parts and continues the game with the remaining part. Specifically, in the first round, Yuki splits and Yuki deletes; in the second round, K splits and K deletes; in the third round, Yuki splits and Yuki deletes again. 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 4 numbers and the right 1 number, she can directly delete the left part, leaving the maximum value. | 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$.