Единственная разница в легкой и сложной версии это ограничение на количество запросов.
Это интерактивная задача.
Есть массив \(a\) из \(n\) различных чисел. За один запрос вы можете узнать позицию второго максимума на подотрезке \(a[l..r]\). Найдите позицию максимального элемента в массиве за не более чем 40 запросов.
Подотрезком \(a[l..r]\) называются все элементы \(a_l, a_{l + 1}, ..., a_r\). После запроса этого подотрезка на ввод вы получите позицию второго максимума из этого подотрезка во всём массиве.
Протокол взаимодействия
Вы можете делать запросы посредством вывода «? \(l\) \(r\)» \((1 \leq l < r \leq n)\). Ответом будет выведена позиция второго максимума среди элементов \(a_l, a_{l + 1}, \ldots, a_r\). Массив \(a\) заранее зафиксирован и не может быть изменен во время интеракции.
Вы можете вывести ответ, выведя «! \(p\)», где \(p\) — индекс максимального элемента во всем массиве.
Вы можете сделать не более 40 запросов. Вывод ответа не считается за запрос.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Для того, чтобы сделать взлом, используйте следующий формат теста.
В первой строке выведите одно целое число \(n\) \((2 \leq n \leq 10^5)\). Во второй строке выведите перестановку \(n\) целых чисел от \(1\) до \(n\). Позиция числа \(n\) в перестановке и будет позицией максимума.
Примечание
В примере представьте, что \(a\) это \([5, 1, 4, 2, 3]\). Так, после запроса подотрезка \([1..5]\) элемент со значением \(4\) является вторым по значению и стоит на позиции \(3\). После запроса подтрезка \([4..5]\) элемент со значением \(2\) является вторым по значению и стоит на позиции \(4\) во всём массиве.
Заметьте, что существуют другие массивы \(a\), для которых интеракция выглядит точно также, а ответ может быть другим. Пример вывода дан для понимания интеракции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
4
|
? 1 5
? 4 5
! 1
|