F. Circular Minesweeper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Interactive problem

You are given a circle of $$$L = 10^9$$$ cells, numbered around the circle from $$$1$$$ to $$$L$$$ (cells $$$1$$$ and $$$L$$$ are adjacent). There are mines in $$$n$$$ distinct cells; in each test, the mine placement is chosen randomly and uniformly among all sets of $$$n$$$ cells.

You may probe cells. If the probed cell contains a mine, it explodes. In response to a probe of cell $$$i$$$, you learn whether there was a mine there, and the distance $$$d$$$ from $$$i$$$ to some remaining unexploded mine. Which mine is chosen is determined by an unknown rule — it is not necessarily the nearest mine. The distance between cells $$$a$$$ and $$$b$$$ is $$$\min(|a - b|,\, L - |a - b|)$$$.

After making at most $$$30$$$ probes, specify a cell that definitely contains an unexploded mine.

Input

The first line contains an integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — the number of mines.

Output

See the section "Interaction protocol".

Interaction

First read the number $$$n$$$.

To make a probe, output "? i" $$$(1 \le i \le L)$$$ and read the response:

  • "YES d", if cell $$$i$$$ contained a mine (and it exploded),
  • "NO d", if there was no mine.

Here $$$d$$$ is the distance from $$$i$$$ to some unexploded mine; the mine exploded by this probe is not taken into account.

You can make at most $$$30$$$ probes. To give the final answer, output "! i" and terminate the program: at that moment, cell $$$i$$$ must contain an unexploded mine. The final answer does not count toward the probe limit.

Your program will receive the verdict "Wrong answer" in the following cases:

  • the output format is invalid;
  • the number of available probes is exceeded;
  • all mines have exploded;
  • the output answer is incorrect (the cell does not contain an unexploded mine).

After each query, you must flush the output buffer, otherwise your program will receive the verdict "Idleness Limit Exceeded":

  • C++: std::endl when using iostream (cout « ... « endl), fflush(stdout) after output using stdio (printf);
  • Java: System.out.println(...), and when using another stream (PrintWriter, BufferedWriter) — call its flush() after each line;
  • Python: print(..., flush=True), and read the interactor's responses using input().
Example
Interaction log
> 4
< ? 1
> YES 4
< ? 1
> NO 11
< ? 13
> NO 1
< ! 12
Note

Example. There are mines in cells $$$1$$$, $$$5$$$, $$$12$$$, and $$$100$$$ on the circle (the program does not know these positions; it only sees $$$n = 4$$$).

  • For the query "? 1", the interactor responds "YES 4": cell $$$1$$$ contained a mine and it exploded (the distances to mines $$$5$$$, $$$12$$$, and $$$100$$$ are $$$4$$$, $$$11$$$, and $$$99$$$ respectively; the interactor chose mine $$$5$$$ and returned the distance to it);
  • For the repeated query "? 1", the interactor responds "NO 11": there is no mine in cell $$$1$$$ anymore, and the distance to mine $$$12$$$, which the interactor chose, is $$$11$$$;
  • For the query "? 13", the interactor responds "NO 1": there is no mine in cell $$$13$$$, the interactor chose mine $$$12$$$ and returned the distance to it;
  • the program outputs "! 12" and terminates — the answer is correct, since this cell contains an unexploded mine. In total, $$$3$$$ probes were made out of the allowed $$$30$$$ (the query "! 12" does not count toward this limit).

This example shows that the distance $$$d$$$ in the interactor's response is the distance to some (not necessarily the nearest) unexploded mine, and that you cannot output an already exploded mine as the answer.

The strategy for finding an unexploded mine used in the example is not necessarily optimal.