311171: CF1944C. MEX Game 1

C. MEX Game 1time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

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.

ExampleInput

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

Output

2
1
0

Note

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.

题目大意：
Alice和Bob在一个包含n个整数的数组a上玩游戏。Alice从一个空数组c开始。两个玩家轮流进行游戏，Alice先开始。

在Alice的回合，她从a中选择一个元素，将其添加到c的末尾，并从a中删除它。
在Bob的回合，他从a中选择一个元素，并从a中删除它。
当数组a为空时，游戏结束。游戏的得分定义为c的MEX（最小排除数）。Alice想要最大化得分，而Bob想要最小化得分。如果两个玩家都进行最优游戏，求游戏的最终得分。

MEX（最小排除数）的定义是：对于一组整数，它是这组整数中没有出现的最小非负整数。例如：
- [2,2,1]的MEX是0，因为0不在数组中。
- [3,1,0,1]的MEX是2，因为0和1在数组中，但2不在。
- [0,3,1,2]的MEX是4，因为0, 1, 2和3在数组中，但4不在。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）。
每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i 保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，如果两个玩家都进行最优游戏，输出游戏的得分。

示例输入：
```
3
4
0 0 1 1
4
0 1 2 3
2
1 1
```

示例输出：
```
2
1
0
```题目大意： Alice和Bob在一个包含n个整数的数组a上玩游戏。Alice从一个空数组c开始。两个玩家轮流进行游戏，Alice先开始。 在Alice的回合，她从a中选择一个元素，将其添加到c的末尾，并从a中删除它。 在Bob的回合，他从a中选择一个元素，并从a中删除它。 当数组a为空时，游戏结束。游戏的得分定义为c的MEX（最小排除数）。Alice想要最大化得分，而Bob想要最小化得分。如果两个玩家都进行最优游戏，求游戏的最终得分。 MEX（最小排除数）的定义是：对于一组整数，它是这组整数中没有出现的最小非负整数。例如： - [2,2,1]的MEX是0，因为0不在数组中。 - [3,1,0,1]的MEX是2，因为0和1在数组中，但2不在。 - [0,3,1,2]的MEX是4，因为0, 1, 2和3在数组中，但4不在。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）。 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i