G3. Дореми и идеальная пара по структурам данных (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между этой задачей и другими двумя версиями — максимальное количество запросов. В этой версии вы можете сделать не более $$$\mathbf{20}$$$ запросов. Вы можете делать взломы только в том случае, если все версии задачи решены.

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

«Все-все! Идеальная пара Дореми по структурам данных уже начинается! Присаживайтесь и хорошо поработайте, если хотите иметь такой же IQ, как у меня!» На сегодняшней паре Дореми рассказывает о могущественной структуре данных: дереве Дореми! И прямо сейчас она дает вам задание, чтобы проверить, насколько вы внимательно слушаете.

Пусть есть массив целых чисел $$$a$$$ длины $$$m$$$. Дерево Дореми поддерживает запросы $$$Q(l,r,k)$$$, где $$$1 \leq l \leq r \leq m$$$ и $$$1 \leq k \leq m$$$, которые возвращают количество различных целых чисел в массиве $$$\left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right]$$$.

Дореми загадала перестановку $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. Вы можете делать запросы, в одном запросе вы задаете $$$3$$$ целых числа $$$l,r,k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$) и получаете в ответ значение $$$Q(l,r,k)$$$ для массива $$$p$$$. Можете ли вы найти индекс $$$y$$$ ($$$1 \leq y \leq n$$$) такой, что $$$p_y=1$$$, за не более чем $$$\mathbf{20}$$$ запросов?

Обратите внимание, что перестановка $$$p$$$ зафиксирована до начала взаимодействия.

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

В начале взаимодействия считайте целое число $$$n$$$ ($$$3 \le n \le 1024$$$) в первой строке — длину перестановки.

Чтобы сделать запрос, выведите

  • «? $$$l\ r\ k$$$» ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$)
на отдельной строке. После вывода запроса считайте целое число $$$x$$$ — значение $$$Q(l,r,k)$$$ для перестановки $$$p$$$. Вы можете сделать не более $$$20$$$ таких запросов.

Чтобы вывести ответ, выведите

  • «! $$$y$$$» ($$$1 \leq y \leq n$$$)
на отдельной строке, где $$$p_y=1$$$.

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

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

Формат взломов

Первая строка должна содержать одно целое число $$$n$$$ ($$$3 \le n \le 1024$$$) — длину перестановки.

Вторая строка должна содержать $$$n$$$ различных целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i\le n$$$) — загаданную перестановку.

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

2

2

1

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

? 1 3 4

? 3 5 3

? 3 4 5

? 3 5 2

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

Перестановка в примере равна $$$[3,5,2,1,4]$$$.

Примеры ввода и вывода иллюстрируют возможное взаимодействие в примере (дополнительные переводы строк добавлены только для удобства чтения).

В этом взаимодействии:

  • В первом запросе $$$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=0$$$, поэтому ответ равен $$$2$$$.
  • Во втором запросе $$$\lfloor\frac{2}{3}\rfloor=0,\lfloor\frac{1}{3}\rfloor=0,\lfloor\frac{4}{3}\rfloor=1$$$, поэтому ответ равен $$$2$$$.
  • В третьем запросе $$$\lfloor\frac{2}{5}\rfloor=0,\lfloor\frac{1}{5}\rfloor=0$$$, поэтому ответ равен $$$1$$$.
  • В четвертом запросе $$$\lfloor\frac{2}{2}\rfloor=1,\lfloor\frac{1}{2}\rfloor=0,\lfloor\frac{4}{2}\rfloor=2$$$, поэтому ответ равен $$$3$$$.

После $$$4$$$ запросов был выведен правильный ответ, поэтому это взаимодействие будет зачтено.