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

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

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.

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