Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×
C. salyg1n и игра с MEX
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача!

salyg1n подарил Алисе множество S из n различных целых чисел s1,s2,…,sn (0≤si≤109). Алиса решила сыграть против Боба в игру с этим множеством. Правила игры таковы:

  • Игроки ходят по очереди, первой ходит Алиса.

  • Алиса за один ход добавляет в множество S одно число x (0≤x≤109). Множество S не должно содержать число x на момент хода.
  • Боб за один ход удаляет из множества S одно число y. Множество S должно содержать число y на момент хода. Также число y должно быть строго меньше последнего добавленного Алисой числа.
  • Игра заканчивается, когда Боб не может сделать ход или спустя 2⋅n+1 ходов (в таком случае последним ходом будет ход Алисы).
  • Результатом игры назовем MEX†(S) (S на момент конца игры).
  • Алиса стремится максимизировать результат, а Боб минимизировать.

Пусть R — результат при оптимальной игре обоих игроков. В этой задаче вы играете за Алису против программы жюри, играющей за Боба. Ваша задача — реализовать стратегию Алисы, при которой результат игры всегда будет не меньше R.

† MEX набора чисел c1,c2,…,ck определяется как наименьшее неотрицательное целое число x, которое не встречается в наборе чисел c. Например, MEX({0,1,2,4}) = 3.

Входные данные

В первой задано одно целое число t (1≤t≤105) — количество тестовых случаев.

Протокол взаимодействия

Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания целого числа n (1≤n≤105) — размера множества S до начала игры.

Затем считайте одну строку — n различных целых чисел si (0≤s1<s2<…<sn≤109) — множество S подаренное Алисе.

Чтобы сделать ход выведите целое число x (0≤x≤109) — число которое вы хотите добавить в множество S. S не должно содержать x на момент хода. Затем считайте одно целое число y (−2≤y≤109).

  • Если 0≤y≤109 — Боб удаляет число y из множества S. Ваш ход!
  • Если y = −1 — игра закончена. После этого следует приступать к обработке следующего тестового случая или завершить программу, если это был последний тестовый случай.
  • Иначе y = −2. Это значит, что вы сделали некорректный запрос. Ваша программа должна немедленно завершится, чтобы получить вердикт Неправильный ответ. Иначе она может получить любой другой вердикт.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.
Гарантируется, что сумма n по всем тестовым случаям не превосходит 105.

По этой задаче нельзя делать взломы.

Пример
Входные данные
3
5
1 2 3 5 7

7

5

-1

3
0 1 2

0

-1

3
5 7 57

-1
Выходные данные
8

57

0

3

0

0
Примечание

В первом наборе входных данных множество S менялось так:

{1,2,3,5,7} → {1,2,3,5,7,8} → {1,2,3,5,8} → {1,2,3,5,8,57} → {1,2,3,8,57} → {0,1,2,3,8,57}. В конце игры, MEX(S)=4, R=4.

Во втором наборе входных данных множество S менялось так:

{0,1,2} → {0,1,2,3} → {1,2,3} → {0,1,2,3}. В конце игры, MEX(S)=4, R=4.

В третьем наборе входных данных множество S менялось так:

{5,7,57} → {0,5,7,57}. В конце игры, MEX(S)=1, R=1.