Minimum Queries

Limits: 2 sec., 512 MiB

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.

Input

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\).

Output

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.

Constraints

\(1 \le m \le n \le 10^4\).

Notes

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\).