O. Дом для червячка

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

Вы ищете место для червячка Максимуса. Участок земли — полоска из $n$ клеток; у клетки $i$ есть влажность $h_i$, которую можно измерить сканером. За пределами полоски влажность считается нулевой.

Максимус любит влажную почву и не сдвинется с места, только если его клетка не суше обоих соседей. Найдите локальный максимум — клетку $i$, для которой $h_i \ge h_{i-1}$ и $h_i \ge h_{i+1}$, — сделав не более $q$ измерений.

В начале взаимодействия считайте два числа $n$ и $q$ ($1 \le n \le 2 \cdot 10^5$) — длину полоски и разрешённое число измерений.

Чтобы измерить влажность, выведите ? i ($1 \le i \le n$) — в ответ придёт $h_i$ ($1 \le h_i \le 10^9$).

Найдя подходящую клетку, выведите ! i и завершите работу.

Измерений не больше $q$. После каждого вывода делайте flush.