Codeforces Round 968 (Div. 2) |
---|
Finished |
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:
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.
521 231 1 231 2 353 1 2 2 31010 2 5 2 7 9 2 5 10 7
2 1 2 2 7
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:
In the fourth test case, one of the possible game processes is as follows:
Name |
---|