A. A boring party!
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Your friend Lina invited you and a bunch of other friends to a costume party to celebrate her success in writing her first program, called "Hello World!". Since the party was boring, you decided to try and guess Lina's position before the celebration comes to an end.

Strangely enough, your friends were standing in a line numbered from $$$1$$$ to $$$N$$$, consecutively from left to right. Initially, no one knows where Lina is, other than her. You can perform the following action at most $$$10^5$$$ times (or the party will be over):

Select one person, ask them where Lina is. If they don't know the answer (or the person is Lina), they will answer with $$$0$$$. Otherwise, they will return:

  • $$$-1$$$ (indicating that Lina's position is greater than theirs), or
  • $$$1$$$ (indicating that Lina's position is smaller than theirs).

After each query, everyone who knows Lina's position will spread this information to the people next to them (at most two new people will know Lina's position after each query).

Keep in mind that the program is designed to challenge you. Lina can be in any position that is consistent with the answers you receive, so be cautious with your queries.

Your goal is to find Lina's position using as few queries as possible.

Input

The first line contains an integer $$$N (1\leq N\leq 10^5)$$$ – the number of people at the party.

Interaction

To inquire about the position of friend number $$$i$$$ ($$$1 \leq i \leq N$$$), use the format: "? i". The interactor will respond with:

  • $$$0$$$ if the person doesn't know where Lina is (or if the person is Lina),
  • $$$-1$$$ if Lina's position is greater than the queried person's position,
  • $$$1$$$ if Lina's position is smaller than the queried person's position.

To make a guess about Lina's position, use the format: "! i" ($$$1 \leq i \leq N$$$). You can only make one guess. The interactor will not respond to the guess, and your program should terminate immediately after making the guess.

Keep in mind that the grader is adaptive, meaning it will adjust its behavior based on your queries. Therefore, your queries influence the responses.

After each query or guess, remember to output a newline and flush the output to avoid an idleness limit exceeded verdict. In C++, you can do this with: fflush(stdout) or cout.flush().

Scoring

Your score will be calculated based on the maximal value of $$$Q$$$, the number of queries made.

  • If $$$Q \gt 10^5:$$$ $$$\textrm{Score} = 0$$$.
  • If $$$470 \lt Q\leq 10^5:$$$ $$$\textrm{Score}=5+ 95\left(1-\sqrt{\dfrac{Q}{10^5}}\right)$$$
  • If $$$Q\leq 470:$$$ $$$\textrm{Score} =100$$$.
Example
Input
5
0
-1
1
0
Output
? 3
? 2
? 5
? 3
! 3
Note

In the sample test, there are 5 people, and Lina is at position 3.

  • At the beginning, no one except Lina knew her position. If you asked anyone at this stage, their responses would be: $$$0, 0, 0,0,0$$$. So the answer to the first query "? $$$3$$$" was $$$0$$$.
  • After the first query, Lina revealed her position to her immediate neighbors (positions 2 and 4). The responses became: $$$0,-1,0,1,0$$$. So the answer to the second query "? $$$2$$$" was $$$-1$$$.
  • After the second query, the people who knew Lina's position (positions 2, 3, and 4) spread this information further to their neighbors (positions 1 and 5). The responses then became: $$$-1,-1,0,1,1$$$. So the answer to the third query "? $$$5$$$" was $$$1$$$.
  • After the third query, since everyone now knows Lina's position, no new information was revealed, so the answers remained unchanged: $$$-1,-1,0,1,1$$$. So the answer to the last query "? $$$3$$$" was $$$0$$$.
  • After that, the user successfully guessed Lina's position "! $$$3$$$"