Minimum Queries

Обмеження: 2 сек., 512 МіБ

This is an interactive task, where your program and the judge interact via standard input and output.

The judge has a permutation $p$ of integers $(1, 2, \dots, n)$.

You are given two integers $n$ and $m$. The permutation $p$ is not given to you.

You can ask the judge at most $n - 1$ following questions.

• Choose two integers $l$ and $r$ such that $1 \le l \le r \le n$ and ask the index $i$ such that $l \le i \le r$ and $p_i \le p_j$ for all $l \le j \le r$. In other words, ask the position of the minimum element in the range $p[l, r]$.

Find the index $k$ such that $p_k = m$. If it is impossible to find it, report this.

Вхідні дані

First, receive two integers $n$ and $m$ from standard input.

Then, you get to ask the judge at most $n - 1$ questions as described in the problem statement.

Print each question to standard output in the format "? $\ l \ r$", where $l, r$ are integers satisfying $1 \le l \le r \le n$.

In response to this, the answer to your question – the index $i$ – will be given from standard input. Here, $l \le i \le r$.

Вихідні дані

When you find the index $k$ satisfying $p_k = m$, print it in the format "!$\ k$".

If it is impossible to find this index, print ! -1.

Обмеження

$1 \le m \le n \le 10^4$.

Примітки

Print a newline and flush standard output at the end of each message.

After printing the answer, immediately quit the program.

The permutation $p$ will be fixed at the start of the interaction and will not be changed according to your questions or other factors.

In the following interaction, $n = 7$, $m = 3$, and $p = (1, 3, 5, 6, 4, 7, 2)$.

Input	Output	Description
7 3		$n$ and $m$ are given.
	? 1 7	Ask the position of the minimum in the range $p[1, 7]$.
1		The judge responds with $i = 1$.
	? 4 4	Ask the position of the minimum in the range $p[4, 4]$.
4		The judge responds with $i = 4$.
	? 2 7	Ask the position of the minimum in the range $p[2, 7]$.
7		The judge responds with $i = 7$.
	? 2 6	Ask the position of the minimum in the range $p[2, 6]$.
2		The judge responds with $i = 2$.
	! 2	Print $k = 2$ as the answer.

For $k = 2$, we have $p_k = m$. Thus, if the program immediately quits here, this case will be judged as correctly solved.

Here is another example with $n = 4$, $m = 2$, and $p = (2, 1, 4, 3)$.

Input	Output	Description
4 2		$n$ and $m$ are given.
	? 1 4	Ask the position of the minimum in the range $p[1, 4]$.
2		The judge responds with $i = 2$.
	! -1	Print -1 as the answer since it is impossible to find the index $k$ such that $p_k = m$.