Это интерактивная задача.
Жюри загадало перестановку\(^\dagger\) \(p\) длины \(n\).
В один запрос можно выбрать два целых числа \(l\) и \(r\) (\(1 \le l < r \le n\)), заплатив за это \((r - l)^2\) монет. В ответ вы получите количество инверсий\(^\ddagger\) в подмассиве \([p_l, p_{l + 1}, \ldots p_r]\).
Найдите индекс максимального элемента в \(p\), потратив не более \(5 \cdot n^2\) монет.
Примечание: интерактор не является адаптивным: перестановка фиксируется до выполнения каких-либо запросов.
\(^\dagger\) Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
\(^\ddagger\) Количеством инверсий в массиве является количество пар индексов \((i,j)\) таких, что \(i < j\) и \(a_i > a_j\). Например, массив \([10,2,6,3]\) содержит \(4\) инверсии: \((1,2),(1,3),(1,4)\) и \((3,4)\).
Протокол взаимодействия
Взаимодействие для каждого набора входных данных начинается с чтения целого числа \(n\).
Для формирования запроса выведите «? l r» (\(1 \le l < r \le n\)) без кавычек. После этого вы должны прочитать одно единственное целое число — ответ на ваш запрос.
Если вместо ответа или допустимого значения \(n\) вы получите целое число \(-1\), то это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неверный ответ на предыдущем наборе входных данных. При получении вердикта «Неправильный ответ» ваша программа должна немедленно завершиться. В противном случае можно получить произвольный вердикт, поскольку решение будет продолжать считывать данные из закрытого потока.
Когда вы будете готовы дать окончательный ответ, выведите «! i» (\(1 \le i \le n\)) без кавычек — индекс максимума загаданной перестановки. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Для взлома используйте следующий формат:
Первая строка содержит целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(2 \le n \le 2000\)) — длина скрытой перестановки \(p\).
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(p_1,p_2,\ldots, p_n\) (\(1 \le p_i \le n\)), причем \(p\) должно быть перестановкой.
Сумма \(n\) по всем наборам входных данных не должна превышать \(2000\).
Примечание
В первом тесте взаимодействие происходит следующим образом:
| Решение | Жюри | Объяснение |
| 2 | Имеется \(2\) набора входных данных. |
| 4 | В первом наборе входных данных загадана перестановка \([1,3,2,4]\) длины \(4\). |
| ? 1 3 | 1 | Решение запрашивает количество инверсий в подмассиве \([1,3,2]\), заплатив \(4\) монеты, а жюри отвечает \(1\). |
| ? 3 4 | 0 | Решение запрашивает количество инверсий в подмассиве \([2,4]\), заплатив \(1\) монету, а жюри отвечает \(0\). |
| ! 4 | | Решение каким-то образом определило, что \(p_4 = 4\), и выводит это. Поскольку ответ правильный, жюри переходит к следующему набору входных данных. |
| 2 | Во втором наборе входных данных загадана перестановка \([2,1]\) длины \(2\). |
| ? 1 2 | 1 | Решение запрашивает количество инверсий в подмассиве \([2,1]\), заплатив \(1\) монету, а жюри отвечает \(1\). |
| ! 1 | | Решение каким-то образом определило, что \(p_1 = 2\), и выводит это. Поскольку ответ верен и наборов входных данных больше нет, жюри и решение завершаются. |
|
Обратите внимание, что пустые строки во входных и выходных данных примера сделаны для наглядности и не встречаются в реальном взаимодействии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
1
0
2
1
|
? 1 3
? 3 4
! 4
? 1 2
! 1
|