CF1867C.Salyg1n and the MEX Game

This is an interactive problem!

salyg1n gave Alice a set $S$ of $n$ distinct integers $s_1, s_2, \ldots, s_n$ ($0 \leq s_i \leq 10^9$). Alice decided to play a game with this set against Bob. The rules of the game are as follows:

• Players take turns, with Alice going first.

• In one move, Alice adds one number $x$ ($0 \leq x \leq 10^9$) to the set $S$. The set $S$ must not contain the number $x$ at the time of the move.

• In one move, Bob removes one number $y$ from the set $S$. The set $S$ must contain the number $y$ at the time of the move. Additionally, the number $y$ must be strictly smaller than the last number added by Alice.

• The game ends when Bob cannot make a move or after $2 \cdot n + 1$ moves (in which case Alice's move will be the last one).

• The result of the game is $\operatorname{MEX}\dagger(S)$ ($S$ at the end of the game).

• Alice aims to maximize the result, while Bob aims to minimize it.

Let $R$ be the result when both players play optimally. In this problem, you play as Alice against the jury program playing as Bob. Your task is to implement a strategy for Alice such that the result of the game is always at least $R$.

$\dagger$ $\operatorname{MEX}$ of a set of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the set $c$. For example, $\operatorname{MEX}({0, 1, 2, 4})$ $=$ $3$.

这是一个交互式问题！

salyg1n 给了 Alice 一个包含 $n$ 个互不相同整数 $s_1, s_2, \ldots, s_n$ 的集合 $S$（其中 $0 \leq s_i \leq 10^9$）。Alice 决定用该集合与 Bob 进行一场博弈。游戏规则如下：

• 双方轮流行动，Alice 先手。

• 在一次行动中，Alice 向集合 $S$ 中添加一个数 $x$（$0 \leq x \leq 10^9$）。在行动时，集合 $S$ 中不能已含有该数 $x$。

• 在一次行动中，Bob 从集合 $S$ 中移除一个数 $y$。在行动时，集合 $S$ 中必须已含有该数 $y$；此外，该数 $y$ 必须严格小于 Alice 上一次所添加的数。

• 当 Bob 无法行动，或总行动次数达到 $2 \cdot n + 1$ 次时，游戏结束（此时 Alice 的行动为最后一次）。

• 游戏的得分为 $\operatorname{MEX}\dagger(S)$（即游戏结束时集合 $S$ 的 $\operatorname{MEX}$ 值）。

• Alice 的目标是使得分尽可能大，而 Bob 的目标是使得分尽可能小。

设 $R$ 为双方均采取最优策略时的游戏结果。本题中，你将扮演 Alice，而评测程序将扮演 Bob。你的任务是实现一种 Alice 的策略，使得游戏结果始终至少为 $R$。

$\dagger$ 一组整数 $c_1, c_2, \ldots, c_k$ 的 $\operatorname{MEX}$ 定义为未出现在该集合中的最小非负整数 $x$。例如，$\operatorname{MEX}({0, 1, 2, 4}) = 3$。

The first line contains an integer $t$ ($1 \leq t \leq 10^5$) - the number of test cases.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）——测试用例的数量。

In the first test case, the set $S$ changed as follows:

{$1, 2, 3, 5, 7$} $\to$ {$1, 2, 3, 5, 7, 8$} $\to$ {$1, 2, 3, 5, 8$} $\to$ {$1, 2, 3, 5, 8, 57$} $\to$ {$1, 2, 3, 8, 57$} $\to$ {$0, 1, 2, 3, 8, 57$}. In the end of the game, $\operatorname{MEX}(S) = 4$, $R = 4$.

In the second test case, the set $S$ changed as follows:

{$0, 1, 2$} $\to$ {$0, 1, 2, 3$} $\to$ {$1, 2, 3$} $\to$ {$0, 1, 2, 3$}. In the end of the game, $\operatorname{MEX}(S) = 4$, $R = 4$.

In the third test case, the set $S$ changed as follows:

{$5, 7, 57$} $\to$ {$0, 5, 7, 57$}. In the end of the game, $\operatorname{MEX}(S) = 1$, $R = 1$.

在第一个测试用例中，集合 $S$ 的变化过程如下：

{$1, 2, 3, 5, 7$} $\to$ {$1, 2, 3, 5, 7, 8$} $\to$ {$1, 2, 3, 5, 8$} $\to$ {$1, 2, 3, 5, 8, 57$} $\to$ {$1, 2, 3, 8, 57$} $\to$ {$0, 1, 2, 3, 8, 57$}。游戏结束时，$\operatorname{MEX}(S) = 4$，$R = 4$。

在第二个测试用例中，集合 $S$ 的变化过程如下：

{$0, 1, 2$} $\to$ {$0, 1, 2, 3$} $\to$ {$1, 2, 3$} $\to$ {$0, 1, 2, 3$}。游戏结束时，$\operatorname{MEX}(S) = 4$，$R = 4$。

在第三个测试用例中，集合 $S$ 的变化过程如下：

{$5, 7, 57$} $\to$ {$0, 5, 7, 57$}。游戏结束时，$\operatorname{MEX}(S) = 1$，$R = 1$。