Problem Statement

This is an interactive problem.

At a regional site, each chair will break if it is subjected to a weight exceeding a non-negative integer $k$. However, you don’t know the value of $k$; you only know a positive integer $n$ such that $0 \le k \le n$.

You have two identical chairs available for testing. You can place any weight on each chair to determine whether it will break.

You may ask at most $\lceil \sqrt{2n} + 5 \rceil$ queries. In each query, you choose a weight $x$ and learn whether that weight causes a chair to break. Note that if a chair breaks, you cannot use it for further queries, and if both chairs break, you cannot make any more queries.

Your task is to find the exact value of $k$. Specifically, you need to output an integer $x$ such that $0 \le x \le n$ and $x$ does not break the chair, but $x + 1$ does.

$\lceil x \rceil$ represents the ceiling function of $x$, which rounds $x$ up to the nearest integer.

Input Format

Interaction

Initially, you will read an integer $n$ ($1 \leq n \leq 10^9$), representing the upper bound for $k$. Then you begin querying to find $k$.

In the guessing process, you may ask at most $\lceil \sqrt{2n} + 5 \rceil$ queries. Each query should be formatted as:

• ? x, where $x$ is an integer such that $0 \leq x \leq n$.

For each query, one of the following responses will be returned:

• If $x \leq k$, it returns 0, indicating the chair did not break.
• If $x > k$, it returns 1, indicating the chair broke.

When you are certain of the value of $k$, you should output your answer as follows:

• ! x, where $x$ is your guess for $k$ ($0 \leq x \leq n$).

Then your program should terminate.

Note:

• If you exceed the maximum number of $\sqrt{2n} + 5$ queries or submit an incorrect answer, you will receive -1 and the solution will be judged as Wrong Answer. In this case, your program should terminate immediately to avoid unnecessary consequences.
• You have only two chairs, so after accumulating two responses of 1, all subsequent queries will return -1, which is also considered Wrong Answer.

After each query or answer output, remember to print a newline and flush the output buffer to avoid Time Limit Exceeded errors. You can flush the output buffer as follows:

• In C++, use fflush(stdout) or cout.flush().
• In Java, use System.out.flush().
• In Pascal, use flush(output).
• In Python, use sys.stdout.flush().
• For other languages, refer to the respective documentation.

Output Format

Example

Example Input

10

1

0

0

0

1

Example Output

? 5

? 1

? 2

? 3

? 4

! 3

Constraints

For $25\%$ of the test cases, the interactor is non-adaptive, meaning that $k$ is pre-determined.

For the remaining $75\%$ of the test cases, the interactor is adaptive, meaning that the interactor does not initially have a fixed answer for $k$ but will determine a value during the interaction that meets the problem’s requirements.