Это интерактивная задача.
У жюри была тождественная перестановка \(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\) до запуска вашей программы и не меняет их в зависимости от ваших запросов.
Протокол взаимодействия
Чтобы спросить количество инверсий на отрезке \([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\)).
Примечание
В первом наборе входных данных \(i = 1\), \(j = 3\), \(k = 5\), поэтому последовательность \(a\) равна \([2, 1, 5, 4, 3]\).
Во втором наборе входных данных \(i = 2\), \(j = 4\), \(k = 5\), поэтому последовательность \(a\) равна \([1, 3, 2, 5, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|