311171: CF1944C. MEX Game 1

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:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

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.

3
4
0 0 1 1
4
0 1 2 3
2
1 1

2
1
0

In the first test case, a possible game with a score of $2$ is as follows:

1. Alice chooses the element $1$. After this move, $a=[0,0,1]$ and $c=[1]$.
2. Bob chooses the element $0$. After this move, $a=[0,1]$ and $c=[1]$.
3. Alice chooses the element $0$. After this move, $a=[1]$ and $c=[1,0]$.
4. Bob chooses the element $1$. After this move, $a=[\,]$ and $c=[1,0]$.

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.