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

У вас спрятан массив $$$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;
• смотрите документацию для других языков.