E. Зеркальная дуэль Широ
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этом мире нет такого понятия, как удача. Победитель определяется еще до начала игры.
— No Game No Life

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

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

В начале Сора дает Широ перестановку$$$^{\text{∗}}$$$ $$$p_1,p_2,\ldots,p_n$$$ длины $$$n$$$. В каждой операции Широ может выбрать два различных индекса $$$x$$$ и $$$y$$$ ($$$1\le x\ne y\le n$$$). Затем Сора подбрасывает честную монету:

  • С вероятностью $$$0.5$$$ Сора меняет местами $$$p_x$$$ и $$$p_y$$$;
  • С вероятностью $$$0.5$$$ Сора меняет местами $$$p_{n-x+1}$$$ и $$$p_{n-y+1}$$$.

После операции Сора сообщает фактическую пару индексов, которые были обменяны, чтобы Широ могла обновить свою локальную перестановку соответственно.

Цель Широ — отсортировать перестановку $$$p$$$ в порядке возрастания, используя не более $$$\lfloor 2.5n+800\rfloor$$$ операций. Помогите ей!

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 4000$$$) — длина $$$p$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ — элементы $$$p$$$.

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

Гарантируется, что в этой задаче $$$50$$$ тестов.

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

Для каждого набора входных данных вы можете использовать не более $$$\lfloor 2.5n+800\rfloor$$$ ходов, чтобы отсортировать перестановку $$$p$$$ в порядке возрастания.

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

  • $$$\mathtt{?}\; x\; y$$$ ($$$1 \le x \ne y \le n$$$) — два индекса, которые Широ выбирает на этом ходу.

В ответ на ход вы получите два целых числа $$$u$$$ и $$$v$$$ — фактическая пара индексов, которые Сора поменяла местами. Гарантируется, что $$$(u, v)$$$ случайным образом выбрано из $$$(x, y)$$$ и $$$(n-x+1, n-y+1)$$$ с равной вероятностью.

Чтобы сообщить, что перестановка отсортирована в порядке возрастания, вы должны вывести новую строку с единственным символом $$$\mathtt{!}$$$. Это не считается одним из $$$\lfloor 2.5n+800\rfloor$$$ ходов.

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

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

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

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

1 5

2 1

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



? 1 5

? 4 5

!


!
Примечание

В первом наборе входных данных $$$n=5$$$, и начальная перестановка $$$[5,1,3,4,2]$$$.

  • Мы выводим ? 1 5. Жюри отвечает 1 5, что означает, что позиции $$$1$$$ и $$$5$$$ поменялись местами (без зеркалирования). Массив становится $$$[2,1,3,4,5]$$$.
  • Мы выводим ? 4 5. Жюри отвечает 2 1, что является зеркалированием $$${4,5}$$$, потому что при $$$n=5$$$ мы имеем $$$n-4+1=2$$$ и $$$n-5+1=1$$$. Таким образом, мы должны поменять местами позиции $$$2$$$ и $$$1$$$. Массив становится $$$[1,2,3,4,5]$$$.
  • Перестановка теперь отсортирована, поэтому мы выводим !. Строка ответа не учитывается в лимите операций.

Во втором наборе входных данных данная перестановка уже возрастает, поэтому нам просто нужно вывести !.