Это интерактивная задача.
У вас спрятан массив \(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}\), вы получите вердикт
Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.