Turtle and Piggy Are Playing a Game 2
Contest: Codeforces Round 968 (Div. 2)
Difficulty rating: 800
Tags: games, greedy, sortings

Turtle and Piggy are playing a game on a sequence. They are given a sequence $$$a_1, a_2, \ldots, a_n$$$, and Turtle goes first. Turtle and Piggy alternate in turns (so, Turtle does the first turn, Piggy does the second, Turtle does the third, etc.).

The game goes as follows:

- Let the current length of the sequence be $$$m$$$. If $$$m = 1$$$, the game ends.
- If the game does not end and it's Turtle's turn, then Turtle must choose an integer $$$i$$$ such that $$$1 \le i \le m - 1$$$, set $$$a_i$$$ to $$$\max(a_i, a_{i + 1})$$$, and remove $$$a_{i + 1}$$$.
- If the game does not end and it's Piggy's turn, then Piggy must choose an integer $$$i$$$ such that $$$1 \le i \le m - 1$$$, set $$$a_i$$$ to $$$\min(a_i, a_{i + 1})$$$, and remove $$$a_{i + 1}$$$.

Turtle wants to maximize the value of $$$a_1$$$ in the end, while Piggy wants to minimize the value of $$$a_1$$$ in the end. Find the value of $$$a_1$$$ in the end if both players play optimally.

You can refer to notes for further clarification.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the sequence $$$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 a single integer — the value of $$$a_1$$$ in the end if both players play optimally.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, initially $$$a = [1, 2]$$$. Turtle can only choose $$$i = 1$$$. Then he will set $$$a_1$$$ to $$$\max(a_1, a_2) = 2$$$ and remove $$$a_2$$$. The sequence $$$a$$$ becomes $$$[2]$$$. Then the length of the sequence becomes $$$1$$$, and the game will end. The value of $$$a_1$$$ is $$$2$$$, so you should output $$$2$$$.

In the second test case, one of the possible game processes is as follows:

- Initially $$$a = [1, 1, 2]$$$.
- Turtle can choose $$$i = 2$$$. Then he will set $$$a_2$$$ to $$$\max(a_2, a_3) = 2$$$ and remove $$$a_3$$$. The sequence $$$a$$$ will become $$$[1, 2]$$$.
- Piggy can choose $$$i = 1$$$. Then he will set $$$a_1$$$ to $$$\min(a_1, a_2) = 1$$$ and remove $$$a_2$$$. The sequence $$$a$$$ will become $$$[1]$$$.
- The length of the sequence becomes $$$1$$$, so the game will end. The value of $$$a_1$$$ will be $$$1$$$ in the end.

In the fourth test case, one of the possible game processes is as follows:

- Initially $$$a = [3, 1, 2, 2, 3]$$$.
- Turtle can choose $$$i = 4$$$. Then he will set $$$a_4$$$ to $$$\max(a_4, a_5) = 3$$$ and remove $$$a_5$$$. The sequence $$$a$$$ will become $$$[3, 1, 2, 3]$$$.
- Piggy can choose $$$i = 3$$$. Then he will set $$$a_3$$$ to $$$\min(a_3, a_4) = 2$$$ and remove $$$a_4$$$. The sequence $$$a$$$ will become $$$[3, 1, 2]$$$.
- Turtle can choose $$$i = 2$$$. Then he will set $$$a_2$$$ to $$$\max(a_2, a_3) = 2$$$ and remove $$$a_3$$$. The sequence $$$a$$$ will become $$$[3, 2]$$$.
- Piggy can choose $$$i = 1$$$. Then he will set $$$a_1$$$ to $$$\min(a_1, a_2) = 2$$$ and remove $$$a_2$$$. The sequence $$$a$$$ will become $$$[2]$$$.
- The length of the sequence becomes $$$1$$$, so the game will end. The value of $$$a_1$$$ will be $$$2$$$ in the end.

Example input:
5
2
1 2
3
1 1 2
3
1 2 3
5
3 1 2 2 3
10
10 2 5 2 7 9 2 5 10 7

Example output:
2
1
2
2
7

Editorial:
The problem can be rephrased as follows: the first player can remove a number adjacent to a larger number, while the second player can remove a number adjacent to a smaller number.
To maximize the value of the last remaining number, in the $$$i$$$-th round of the first player's moves, he will remove the $$$i$$$-th smallest number in the sequence, and this is always achievable. Similarly, in the $$$i$$$-th round of the second player's moves, he will remove the $$$i$$$-th largest number.
Thus, the answer is the $$$\left\lfloor\frac{n}{2}\right\rfloor + 1$$$-th smallest number in the original sequence.
Time complexity: $$$O(n \log n)$$$ per test case.