D. Угадай перестановку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

У жюри была тождественная перестановка $$$a$$$ длины $$$n$$$ ($$$a_i = i$$$).

Жюри выбрало три целых числа $$$i$$$, $$$j$$$, $$$k$$$ такие, что $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$. После этого жюри развернуло отрезки $$$[i, j - 1]$$$ и $$$[j, k]$$$ в последовательности $$$a$$$.

Разворачивание подотрезка $$$[l, r]$$$ последовательности $$$a$$$ означает переворот подотрезка элементов $$$a_l, a_{l+1}, \ldots, a_r$$$ в последовательности, то есть $$$a_l$$$ меняется местами с $$$a_r$$$, $$$a_{l+1}$$$ с $$$a_{r-1}$$$, и т. д..

Вам дано число $$$n$$$. Вы должны найти $$$i$$$, $$$j$$$, $$$k$$$ с помощью некоторых запросов.

За один запрос вы можете выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) и узнать количество инверсий на подотрезке $$$[l, r]$$$ последовательности $$$a$$$. Жюри скажет вам количество пар $$$(i, j)$$$ таких, что $$$l \leq i < j \leq r$$$ и $$$a_i > a_j$$$.

Найдите числа $$$i$$$, $$$j$$$, $$$k$$$, выбранные жюри, сделав не более $$$40$$$ запросов.

Жюри фиксирует числа $$$i$$$, $$$j$$$ и $$$k$$$ до запуска вашей программы и не меняет их в зависимости от ваших запросов.

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

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

В единственной строке для каждого набора входных данных дано целое число $$$n$$$ ($$$4 \leq n \leq 10^9$$$). После его считывания, вы должны перейти к процессу взаимодействия с программой жюри и делать запросы. После того, как вы дали ответ, вы должны:

  • Закончить работу программы, если это был последний набор входных данных.
  • Иначе начать работу со следующим набором.
Протокол взаимодействия

Чтобы спросить количество инверсий на отрезке $$$[l, r]$$$, выведите «? l r», где ($$$1 \leq l \leq r \leq n$$$). Вы можете сделать не более $$$40$$$ таких запросов в каждом тестовом случае. В ответ вы получите целое число $$$x$$$.

  • Если $$$x = -1$$$, ваша программа сделала некорректный запрос или превысила допустимое количество запросов для данного набора. В таком случае ваша программа должна немедленно завершиться (иначе решение может получить произвольный вердикт вместо Неправильный ответ).
  • Иначе $$$x$$$ равен количеству инверсий на подотрезке $$$[l, r]$$$ последовательности $$$a$$$.

Чтобы дать ответ, выведите «! i j k», где $$$i$$$, $$$j$$$, $$$k$$$ — числа, которые, как вы считаете, загадало жюри. После этого вы должны перейти к следующему набору или завершить программу.

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

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

Взломы

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

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Каждая из следующих $$$t$$$ строк содержит четыре целых числа $$$n$$$, $$$i$$$, $$$j$$$, $$$k$$$ ($$$4 \leq n \leq 10^9$$$, $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$).

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

4 

3 

3 

5 

2 

2 

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


? 1 5

? 2 5

? 3 5

! 1 3 5

? 1 5

? 2 5

? 3 5

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

В первом наборе входных данных $$$i = 1$$$, $$$j = 3$$$, $$$k = 5$$$, поэтому последовательность $$$a$$$ равна $$$[2, 1, 5, 4, 3]$$$.

Во втором наборе входных данных $$$i = 2$$$, $$$j = 4$$$, $$$k = 5$$$, поэтому последовательность $$$a$$$ равна $$$[1, 3, 2, 5, 4]$$$.