I. Pineapple Upside Down Cake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

For her friend Bob's birthday, Alice is baking him his favorite dessert, pineapple upside down cake!

Even more exciting, Alice has prepared a guessing game for Bob! Alice has placed a secret number of cherries on top of the cake, denoted by a positive integer $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$. The cherries are in a circle around the edge of the cake, and each cherry has a sweetness value. The $$$i^\text{th}$$$ cherry in the circle has sweetness $$$s_i\ (1 \leq s_i \leq 2 \cdot 10^9)$$$, and in fact it is guaranteed that $$$s_1 \lt s_2 \lt \dots \lt s_N$$$, though these values are also unknown to Bob (he only knows that they are strictly increasing).

Alice allows Bob to make a series of at most 50 queries. In the $$$j^\text{th}$$$ query, Bob is allowed to send Alice a positive integer $$$q_j$$$. In response, Alice will tell Bob $$$s_{((q_j - 1) \text{ mod } N) + 1}$$$ (informally, Bob learns the $$$q_j^\text{th}$$$ sweetness value, wrapping around if $$$q_j$$$ is larger than $$$N$$$). After asking his series of queries, Bob's goal is to guess the value of $$$N$$$.

Bob has been having trouble with this daunting task, but he still wants to learn $$$N$$$ so that Alice will reward him with his birthday cake. Please assist him!

Interaction

You are allowed to make at most 50 queries by printing a line containing "? q" $$$(1 \leq q \leq 2 \cdot 10^9)$$$ (without quotes). In return, you may read in a single integer representing $$$s_{((q - 1) \text{ mod } N) + 1}$$$. When you are prepared to guess the value of $$$N$$$, print a single line "! x" $$$(1 \leq x \leq 2 \cdot 10^5)$$$ (without quotes), where $$$x$$$ represents the guess for the value of $$$N$$$, and then exit.

After printing each query (including your final guess) you will need to flush the output stream, because it is possible that some part of your output is left in the buffer. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, flush(output) in Pascal and stdout.flush() in Python. Otherwise, you may get the verdict Idleness limit exceeded.

Exit immediately after receiving -1 and you will see a Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Example
Input
? 1

? 2

? 3

? 4

! 3
Output

1

2

5
Note

The sample test shows an example of interaction in the case where $$$N = 3, s_1 = 1, s_2 = 2$$$, and $$$s_3 = 5$$$. The first three queries yield the values of $$$s_1, s_2$$$, and $$$s_3$$$, and the fourth query yields the value of $$$s_{(3 \text{ mod } 3) + 1} = s_1$$$.