310665: CF1867C. Salyg1n and the MEX Game

C. Salyg1n and the MEX Gametime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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

Interaction

The interaction between your program and the jury program begins with reading an integer $n$ ($1 \leq n \leq 10^5$) - the size of the set $S$ before the start of the game.

Then, read one line - $n$ distinct integers $s_i$ $(0 \leq s_1 < s_2 < \ldots < s_n \leq 10^9)$ - the set $S$ given to Alice.

To make a move, output an integer $x$ ($0 \leq x \leq 10^9$) - the number you want to add to the set $S$. $S$ must not contain $x$ at the time of the move. Then, read one integer $y$ $(-2 \leq y \leq 10^9)$.

• If $0 \leq y \leq 10^9$ - Bob removes the number $y$ from the set $S$. It's your turn!
• If $y$ $=$ $-1$ - the game is over. After this, proceed to handle the next test case or terminate the program if it was the last test case.
• Otherwise, $y$ $=$ $-2$. This means that you made an invalid query. Your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Do not attempt to hack this problem.

ExampleInput

3
5
1 2 3 5 7

7

5

-1

3
0 1 2

0

-1

3
5 7 57

-1

Output

8

57

0

3

0

0

Note

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$.

**题目大意：**

这是一个交互式问题。salyg1n 给了 Alice 一组不同的整数集合 $ S $，其中包含 $ n $ 个整数 $ s_1, s_2, \ldots, s_n $（$ 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}(S) $（游戏结束时 $ S $ 的状态）。
- Alice 的目标是最大化结果，而 Bob 的目标是最小化结果。

定义 $ R $ 为双方都采取最优策略时的结果。在这个问题中，你扮演 Alice，与作为 Bob 的评审程序对战。你的任务是实施一个 Alice 的策略，使得游戏的结果始终至少为 $ R $。

$ \operatorname{MEX} $ 的定义：一个整数集合 $ c_1, c_2, \ldots, c_k $ 的 $ \operatorname{MEX} $ 是指最小的非负整数 $ x $，它不在集合 $ c $ 中出现。例如，$ \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $。

**输入输出数据格式：**

**输入：**

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

**交互：**

你的程序与评审程序之间的交互从读取一个整数 $ n $（$ 1 \leq n \leq 10^5 $）开始——游戏开始前集合 $ S $ 的大小。

然后，读取一行——$ n $ 个不同的整数 $ s_i $（$ 0 \leq s_1 < s_2 < \ldots < s_n \leq 10^9 $）——给 Alice 的集合 $ S $。

为了进行移动，输出一个整数 $ x $（$ 0 \leq x \leq 10^9 $）——你想要添加到集合 $ S $ 中的数字。在移动时，集合 $ S $ 必须不包含 $ x $。然后，读取一个整数 $ y $（$ -2 \leq y \leq 10^9 $）。

- 如果 $ 0 \leq y \leq 10^9 $——Bob 从集合 $ S $ 中移除了数字 $ y $。轮到你了！
- 如果 $ y = -1 $——游戏结束。之后，处理下一个测试用例，或者如果这是最后一个测试用例，则终止程序。
- 否则，$ y = -2 $。这意味着你提出了一个无效的查询。你的程序应该立即终止以获得错误答案的裁决。否则，可能会收到任何其他裁决。

在打印查询后，不要忘记输出换行符并刷新输出。否则，你将得到超时限制。具体操作取决于使用的编程语言。

保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。

**注意：** 不要尝试破解这个问题。**题目大意：** 这是一个交互式问题。salyg1n 给了 Alice 一组不同的整数集合 $ S $，其中包含 $ n $ 个整数 $ s_1, s_2, \ldots, s_n $（$ 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}(S) $（游戏结束时 $ S $ 的状态）。 - Alice 的目标是最大化结果，而 Bob 的目标是最小化结果。 定义 $ R $ 为双方都采取最优策略时的结果。在这个问题中，你扮演 Alice，与作为 Bob 的评审程序对战。你的任务是实施一个 Alice 的策略，使得游戏的结果始终至少为 $ R $。 $ \operatorname{MEX} $ 的定义：一个整数集合 $ c_1, c_2, \ldots, c_k $ 的 $ \operatorname{MEX} $ 是指最小的非负整数 $ x $，它不在集合 $ c $ 中出现。例如，$ \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $。 **输入输出数据格式：** **输入：** 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。 **交互：** 你的程序与评审程序之间的交互从读取一个整数 $ n $（$ 1 \leq n \leq 10^5 $）开始——游戏开始前集合 $ S $ 的大小。 然后，读取一行——$ n $ 个不同的整数 $ s_i $（$ 0 \leq s_1 < s_2 < \ldots < s_n \leq 10^9 $）——给 Alice 的集合 $ S $。 为了进行移动，输出一个整数 $ x $（$ 0 \leq x \leq 10^9 $）——你想要添加到集合 $ S $ 中的数字。在移动时，集合 $ S $ 必须不包含 $ x $。然后，读取一个整数 $ y $（$ -2 \leq y \leq 10^9 $）。 - 如果 $ 0 \leq y \leq 10^9 $——Bob 从集合 $ S $ 中移除了数字 $ y $。轮到你了！ - 如果 $ y = -1 $——游戏结束。之后，处理下一个测试用例，或者如果这是最后一个测试用例，则终止程序。 - 否则，$ y = -2 $。这意味着你提出了一个无效的查询。你的程序应该立即终止以获得错误答案的裁决。否则，可能会收到任何其他裁决。 在打印查询后，不要忘记输出换行符并刷新输出。否则，你将得到超时限制。具体操作取决于使用的编程语言。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **注意：** 不要尝试破解这个问题。