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

Перестановка $p$ длины $n=30000$ скрыта жюри. Ваша задача — найти индекс минимального значения этой перестановки.

Жюри неадаптивно: перестановка выбирается до начала взаимодействия и не меняется.

В отличие от обычных запросов сравнения, жюри сравнивает только ваш текущий запрос с вашим предыдущим запросом. А именно, если ваш предыдущий запрошенный индекс был $i$, а теперь вы запрашиваете индекс $j$, жюри сообщает вам результат сравнения $p_i$ и $p_j$.

Вы можете сделать не более $q_{\max}=42000$ запросов.

Официальные тестовые данные состоят из 100 отдельных файлов. Ваша программа запускается независимо на каждом файле.

Взаимодействие

В начале взаимодействия ваша программа должна прочитать два целых числа

$$ n \quad q_{\max}. $$

Для официальных тестов $n=30000$ и $q_{\max}=42000$.

Чтобы сделать запрос, выведите одну строку в следующем формате:

$$ \text{? j} $$

где $1 \le j \le n$.

Жюри отвечает одним символом:

• < если $p_i < p_j$, где $i$ — предыдущий запрошенный индекс (если применимо);
• =, если это первый запрос, или если $p_i=p_j$;
• >, если $p_i > p_j$, где $i$ — предыдущий запрошенный индекс (если применимо).

Поскольку $p$ — перестановка, ответ = после первого запроса возможен только в том случае, если вы запросили тот же индекс, что и в предыдущем запросе.

Если жюри отвечает -1, ваша программа должна немедленно завершиться. Это означает, что ваша программа нарушила протокол взаимодействия и получит вердикт Wrong Answer.

Чтобы дать окончательный ответ, выведите одну строку в следующем формате:

$$ \text{! a} $$

где $a$ — индекс, который, по вашему утверждению, содержит минимальное значение. После вывода ответа ваша программа должна завершиться. Окончательный ответ не считается запросом.

Если ваша программа сделает более $q_{\max}$ запросов, запросит недопустимый индекс, выведет недопустимую команду или выдаст неверный окончательный ответ, она получит вердикт Wrong Answer.

После каждого вывода запроса или ответа сбрасывайте буфер вывода. Например, в C++ можно использовать endl или cout.flush().

Примечание

Данный пример — лишь иллюстрация взаимодействия и не встретится в реальных тестовых данных. Строки вида (приём ... вывод) являются заполнителями, используемыми только для выравнивания запросов и ответов жюри в примере. В реальном тесте жюри не будет выводить эти строки-заполнители, и участник не должен ни читать, ни выводить их.

В этом примере взаимодействия скрытая перестановка равна $p=(3,1,4,2)$. Пункты ниже описывают взаимодействие, показанное в примере.

• Жюри сначала отправляет $n=4$ и ограничение на запросы $5$.
• Первый запрос ? 1 получает =, потому что нет предыдущего запрошенного индекса.
• Запрос ? 2 сравнивает $p_1=3$ с $p_2=1$, поэтому жюри отвечает >.
• Запрос ? 4 сравнивает $p_2=1$ с $p_4=2$, поэтому жюри отвечает <. Минимум находится на индексе $2$, поэтому ! 2 правильный ответ.

Локальный инструмент взаимодействия: приложенный файл attachments/local_interactive.py может воспроизвести данную локальную настройку с помощью --perm 3,1,4,2 --limit 5, однако успешное прохождение на нём не гарантирует прохождение официальных тестовых данных.