#P2003B. Turtle and Piggy Are Playing a Game 2
Turtle and Piggy Are Playing a Game 2
Description
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.
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$.
For each test case, output a single integer — the value of $a_1$ in the end if both players play optimally.
Input
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
For each test case, output a single integer — the value of $a_1$ in the end if both players play optimally.
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
2
1
2
2
7
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.