MEX Game 1
Description
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.
Input
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$.
Output
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
Note
In the first test case, a possible game with a score of $2$ is as follows:
- Alice chooses the element $1$. After this move, $a=[0,0,1]$ and $c=[1]$.
- Bob chooses the element $0$. After this move, $a=[0,1]$ and $c=[1]$.
- Alice chooses the element $0$. After this move, $a=[1]$ and $c=[1,0]$.
- 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.