Interactive Guessing Game

You are given an integer n and your task is to guess a hidden positive integer q such that \(q \in [1,n]\). You can ask queries of the form ? x y where the interactive system will choose a number \(u \in [x,y]\) and return a pair u v with the following meaning:

• If \(v = 0\), then \(u < q\).
• If \(v = 1\), then \(u = q\).
• If \(v = 2\), then \(u > q\).

The cost for a query ? x y is calculated as \(\dfrac{1}{y-x+1}\). When you are ready to guess, you output your answer in the form ! x, where you believe \(x = q\), and then immediately exit the program.

After every operation you must flush the output buffer. For example, in Python you should use sys.stdout.flush(), in C/C++ use fflush(stdout) or std::cout << std::flush in C++, in Java use System.out.flush(), in Pascal use flush(output), etc.

The score is determined based on your total cost \(x\) as follows (each test case has a full score of 10 points):

• If \(x \le 1.9813035\), you obtain 10 pts.
• If \(1.9813035 < x \le 12\), your score is \(\left\lfloor \frac{(12-x) \times 0.7}{1.00186965} \right\rfloor\) pts.
• If \(x \ge 12\), you get 0 pts.

Note: This is an interactive problem. In a real interactive environment, you would ask queries and receive responses. In our offline simulation, the input will include \(n\) and the hidden number \(q\) (for testing purposes); your program must simply output the guessed number.

inputFormat

The input consists of one or two integers. The first integer is n (\(1 \le n \le 10^9\)). In our offline simulation, the second integer is the hidden value \(q\) (\(1 \le q \le n\)). If the second integer is not provided, you may assume \(q = 1\).

outputFormat

Output your guess in the format: ! x, where you believe x is equal to the hidden number \(q\). Make sure to flush your output buffer immediately after printing the guess.

sample

10 5

! 5