K. Nondecreasing Queries
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden binary string $$$s$$$ of length $$$n$$$. It is guaranteed that $$$s$$$ contains at least one character 1, and you wish to find a 1.

In each query, you may ask if a substring $$$s_ls_{l+1} \ldots s_r$$$ contains a 1. However, there is an additional restriction:

  • If your previous query had length $$$L$$$, then every future query must have length at least $$$L$$$. In other words, the sequence of query lengths must be nondecreasing.

Find the index of any character 1 using at most $$$100$$$ queries.

The length of a query $$$\texttt{?}\;l\; r$$$ is defined as $$$r - l + 1$$$.

Input

At the beginning of the interaction, you are given a single integer $$$n$$$ ($$$1\le n\le 10^4$$$) — the length of the hidden string.

It is guaranteed that the hidden string contains no characters other than 0s and 1s, and that it contains at least one 1.

Interaction

To make a query, print a line in the following format:

  • $$$\texttt{?}\;l\;r$$$ ($$$1\le l\le r\le n$$$) — the indices chosen for the query.

After you print a query, the interactor will respond with a single integer:

  • 1 if the substring $$$s_l s_{l+1}\ldots s_r$$$ contains at least one 1;
  • 0 otherwise.

When you are ready to give the final answer, print a line of the form

  • ! $$$p$$$, where $$$1\le p\le n$$$ and $$$s_p=\texttt{1}$$$,
and flush the output.

If you make an invalid query, ask more than $$$100$$$ queries, or break the nondecreasing-length rule, the interactor may reply with -1. In that case, your program must terminate immediately.

Note that the final answer does not count as a query.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

The interactor is not adaptive; the hidden string is fixed before the interaction starts.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
8

0

1

0
Output

? 4 4

? 6 8

? 5 7

! 8
Note

The hidden string in this test is 00100001.

Note that the lengths of the three queries are $$$1$$$, $$$3$$$, and $$$3$$$ in order. Because $$$s_8 = \texttt{1}$$$, the answer to the query $$$\texttt{?}\;6\;8$$$ is $$$1$$$.