Codeforces Round 934 (Div. 1) |
---|
Finished |
Alice and Bob play yet another game on an array $$$a$$$ of size $$$n$$$. Alice starts with an empty array $$$c$$$. Both players take turns playing, with Alice starting first.
On Alice's turn, she picks one element from $$$a$$$, appends that element to $$$c$$$, and then deletes it from $$$a$$$.
On Bob's turn, he picks one element from $$$a$$$, and then deletes it from $$$a$$$.
The game ends when the array $$$a$$$ is empty. Game's score is defined to be the MEX$$$^\dagger$$$ of $$$c$$$. Alice wants to maximize the score while Bob wants to minimize it. Find game's final score if both players play optimally.
$$$^\dagger$$$ The $$$\operatorname{MEX}$$$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, find game's score if both players play optimally.
340 0 1 140 1 2 321 1
2 1 0
In the first test case, a possible game with a score of $$$2$$$ is as follows:
At the end, $$$c=[1,0]$$$, which has a MEX of $$$2$$$. Note that this is an example game and does not necessarily represent the optimal strategy for both players.
Name |
---|