Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

H. Недостающее число
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Томаса есть массив целых чисел $$$a_1,~\ldots,~a_n$$$, все элементы которого различны и находятся в промежутке от $$$0$$$ до $$$n$$$. Как можно заметить, одного из чисел от $$$0$$$ до $$$n$$$ нет в этом массиве.

Вам нужно найти это число. Вы можете не более $$$2 \cdot n + 19$$$ раз спросить, чему равен $$$b$$$-й бит числа $$$a_i$$$.

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

Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.

В самом начале вашей программе сообщается целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — размер массива.

После этого вы можете сделать не более $$$2 \cdot n + 19$$$ запросов. Чтобы сделать запрос, выведите символ «?», а затем через пробел числа $$$i$$$ и $$$b$$$ ($$$1 \le i \le n, 0 \le b \le \log_{2}n$$$) — индекс $$$i$$$ в массиве и номер бита, который вы хотите узнать. Биты нумеруются с нуля, начиная с младшего.

В ответ на такой запрос сообщается число $$$0$$$ или $$$1$$$ — значение $$$b$$$-го бита числа $$$a_i$$$.

Как только вы определите недостающее в массиве число, выведите символ «!», а затем через пробел это число. После этого ваша программа должна завершиться.

Пример
Входные данные
3

0

1

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

? 1 1

? 2 0

? 3 1

! 2
Примечание

Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.

Пустые строки в примере приведены лишь для удобства, чтобы было лучше понятно, в каком порядке выводятся сообщения. При решении задачи вам не нужно выводить пустые строки, и программа жюри тоже не будет выводить пустые строки.