H. Ожидаемое твист
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

У вас спрятан массив $$$a_1, a_2, \dots, a_n$$$ из $$$n$$$ целых чисел. Ваша задача — найти наименьший элемент массива.

Для этого вы можете задать несколько запросов. В каждом запросе вы можете выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). В ответ вам будет дано значение $$$\max(a_l, a_{l+1}, \dots, a_r)$$$. Иными словами, вам сообщат максимальное значение подмассива от $$$a_l$$$ до $$$a_r$$$.

Найдите минимум массива. Вы можете задать не более $$$\mathbf{624}$$$ запросов.

Гарантируется, что значения $$$a_1, a_2, \dots, a_n$$$ выбираются равномерно случайным образом в диапазоне от $$$0$$$ до $$$2^{32}-1$$$ (включительно).

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

Начните взаимодействие, прочитав целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) на отдельной строке.

Чтобы задать запрос, напечатайте строку в формате $$$\texttt{?}\;\;l\;\;r$$$ ($$$1 \le l \le r \le n$$$). Затем вы должны прочитать одну строку, содержащую ответ на ваш запрос.

После того, как вы определите ответ, напечатайте строку в формате $$$\texttt{!}\;\;x$$$, где $$$x$$$ — минимальное значение.

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

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.
Ответ $$$\texttt{-1}$$$ вместо корректного означает, что ваша программа сделала некорректный запрос или превысила ограничение на число запросов. Ваша программа должна немедленно завершиться после прочтения ответа $$$\texttt{-1}$$$, вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
Пример
Входные данные
3

1295320727

984617979

1295320727

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

? 1 3

? 1 1

? 2 2

? 3 3

! 167316954