Background

This is an interactive problem. The interaction library is adaptive. Please note the special time limit.

Remember to flush the output buffer after every output.

Simplified statement: $\texttt{Link}$.

Problem Description

You need to guess a positive integer $q$, and it is guaranteed that $q\in [1,n]$.

Each time, you may make a query like ? x y, and the interaction library will deliberately choose a number $z$ from $[x,y]$.

Then the interaction library will output an answer in the form u v, meaning that the chosen number is $u$, and its relation to $q$ is $v$.

Specifically:

• When the library returns $v=0$, it means $u<q$.
• When the library returns $v=1$, it means $u=q$.
• When the library returns $v=2$, it means $u>q$.

The cost of one query is $\dfrac{1}{y-x+1}$.

You can output what you believe is the correct answer using ! x.

Now you need to determine $q$.

Let your total cost be $x$. The score you get on each test point depends on your total cost as follows (each test point has a full score of $10$ points):

• If $x\le 1.9813035$, you can get $\text{10 pts}$.
• If $1.9813035 < x \le 12$, you can get $\lfloor(12-x)\times0.7 \div 1.00186965\rfloor \text{ pts}$.
• If $x\ge12$, you can get $\text{0 pts}$.

Note that after every operation, you must call the following function to flush the buffer:

• For C/C++: fflush(stdout).
• For C++: std::cout << std::flush.
• For Java: System.out.flush().
• For Python: stdout.flush().
• For Pascal: flush(output).
• For other languages, please check the corresponding language documentation by yourself.

Interaction Format

At the beginning, the interaction library will give you $n$.

Then you may query or answer as described above.

After you output the answer, please terminate your program immediately.

Input Format

See Interaction Format.

Output Format

See Interaction Format.

2

1 0
 

? 1 2

! 2

3

1 0

3 2
 

? 1 3

? 3 3

! 2

Hint

• Sample $1$ Explanation:

  After querying, we find that $1<x\le2$, so $x=2$.

• Sample $2$ Explanation:

  After the first query, we find that $1<x\le3$.

  After the second query, we find that $1<x<3$, so $x=2$.

【Constraints】

For $100\%$ of the testdata, $1\le n\le10^5$, $1\le q,\forall u\le n$, $\forall v\in\{0,1,2\}$.

It is guaranteed that each query to the interaction library runs in $\mathcal O(1)$ time.

Translated by ChatGPT 5