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

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

Вам дано целое число $$$n$$$. Существует скрытый массив $$$a$$$ длиной $$$2n$$$. Каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз в $$$a$$$. Остальные элементы равны $$$0$$$.

Вы можете делать запросы следующего типа:

  • Выберите два целых числа $$$i$$$ и $$$j$$$ ($$$1 \le i,j \le 2n$$$, $$$i \ne j$$$). Жюри ответит $$$1$$$, если $$$a_i=a_j$$$, и ответит $$$0$$$ в противном случае.

Найдите любое целое число $$$k$$$ ($$$1 \le k \le 2n$$$) такое, что $$$a_k=0$$$, не более чем за $$$n+1$$$ запросов. Обратите внимание, что интерактор является адаптивным, что означает, что скрытый массив $$$a$$$ может изменяться в зависимости от ваших запросов, но не будет противоречить предыдущим запросам.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 10^4$$$). Длина скрытого массива $$$a$$$ будет равна $$$2n$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

Чтобы сделать запрос, выведите строку в следующем формате:

  • $$$\texttt{?}\;i\;j$$$ ($$$1 \le i,j \le 2n$$$, $$$i \ne j$$$)

В ответ на запрос вы получите:

  • $$$1$$$, если $$$a_i=a_j$$$;
  • $$$0$$$, если $$$a_i \ne a_j$$$;
  • $$$-1$$$, если вы сделали недопустимый запрос или если превысили лимит в $$$n+1$$$ запросов.

Чтобы сообщить ответ, выведите строку в следующем формате:

  • $$$\texttt{!}\;k$$$ ($$$1 \le k \le 2n$$$)

После этого переходите к следующему набору входных данных или завершите программу, если это последний набор входных данных.

Обратите внимание, что вывод ответа не учитывается в $$$n+1$$$ запросах.

Интерактор является адаптивным. Это означает, что скрытый массив $$$a$$$ может изменяться в зависимости от ваших запросов, но не будет противоречить предыдущим запросам.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло». На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Для этой задачи взломы отключены.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
2

0

1

3

1

0

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


? 1 2

? 3 1

! 3

? 5 6

? 2 4

? 1 3

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

В первом наборе входных данных скрытый массив $$$a$$$ равен $$$[0,1,0,2]$$$:

  • В первом запросе, $$$(i,j)=(1,2)$$$. Поскольку $$$a_1=0$$$, $$$a_2=1$$$, $$$a_1 \ne a_2$$$, жюри отвечает $$$0$$$.
  • Во втором запросе, $$$(i,j)=(3,1)$$$. Поскольку $$$a_3=0$$$, $$$a_1=0$$$, $$$a_3 = a_1$$$, жюри отвечает $$$1$$$.
  • Программа сообщает $$$k=3$$$ в качестве ответа. Поскольку $$$a_3=0$$$, ответ верный.

Во втором наборе входных данных скрытый массив $$$a$$$ равен $$$[3,2,0,1,0,0]$$$:

  • В первом запросе, $$$(i,j)=(5,6)$$$. Поскольку $$$a_5=0$$$, $$$a_6=0$$$, $$$a_5 = a_6$$$, жюри отвечает $$$1$$$.
  • Во втором запросе, $$$(i,j)=(2,4)$$$. Поскольку $$$a_2=2$$$, $$$a_4=1$$$, $$$a_2 \ne a_4$$$, жюри отвечает $$$0$$$.
  • В третьем запросе, $$$(i,j)=(1,3)$$$. Поскольку $$$a_1=3$$$, $$$a_3=0$$$, $$$a_1 \ne a_3$$$, жюри отвечает $$$0$$$.
  • Программа сообщает $$$k=6$$$ в качестве ответа. Поскольку $$$a_6=0$$$, ответ верный.