L. Let Find The Line
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We all know that the team RUET_Aftermath secured 5th position in ICPC Asia West Continent Final 2021. This is no small feat to achieve and as usual, they got a huge number of fans all over RUET. So, one day they sat at a booth on that "HUGE" road that goes from RUET Gate to Library to give autographs to their fans.

You, being a big fan of theirs, don't want to miss this opportunity. So, you went to the campus as early as possible, but you heard there is already a huge line of fans waiting for the autographs. But you don't know where the line starts or ends and as the road is "HUGE", it's really impossible for you to locate the line without assistance.

Now you asked for help from one random weird guy to find out the length of the line but he will only help you in his weird way. He divided the "HUGE" road into $$$N$$$ equal units numbered from $$$1$$$ to $$$N$$$. The line of fans starts at unit A and ends at unit B where $$${1 \le A \le B \le N}$$$. Now, if you tell the weird guy an integer number from $$$1$$$ to $$$N$$$, he will tell you if the integer is on or before the start, or after the end of the line of fans. And you can ask him at most $$$55$$$ times.

You need to find out the length of the line.

You can assume that the length of the line will not be more than $$$10^{6}$$$.

Interaction

At first, the weird guy will give you the value of $$$N (1 \le N \le 10^9)$$$. You will take this as an integer input.

After that, you have to give him an integer by printing "? $$$x$$$" in a line. In reply he will give you one of these characters :

  • '<' if $$$x$$$ is before the start of the line i.e. $$$x \lt A$$$ .
  • '>' if $$$x$$$ is after the end of the line i.e. $$$x \gt B$$$ .
  • '=' if $$$x$$$ is on the line i.e $$$A \le x \le B$$$ .

You can ask him for help in this way at most at most $$$55$$$ times.

Finally after figuring out the length, just print "! $$$y$$$" in a line, where $$$y$$$ is the length.

Additionally, you must flush your output each time you print a line. You can use,

  • cout.flush() or endl after printing a line in C++
  • fflush(stdout) in C
to flush your output. If you don't flush, you will get Idleness Limit Exceeded verdict.
Examples
Input
6

<

=

=

=

>
Output

? 1

? 2

? 3

? 4

? 5

! 3
Input
1000000000
Output

! 1000000
Note

For the first testcase, the weird guy gives 6 as $$$N$$$. After printing $$$1$$$, the guy tells that it is before the start of the line, and after printing $$$5$$$, the guy tells that it is after the end of the line. And, for $$${2, 4}$$$ and $$$6$$$, the guy tells that these integers are on the line. So, the line started at unit $$$2$$$ and ended at unit $$$4$$$. Thus, the length of the line is $$$3$$$. So, you printed "! 3" as final output.

For the second testcase, the weird guy gives 1000000000 as $$$N$$$. And, somehow you have figured out the length without asking for help from the weird guy.

Note that, it's totally up to you how many questions you'll ask the weird guy but you can't ask more than $$$55$$$ times.