D. Lost Archive
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Galdino downloaded his favorite game on his computer, but he can't remember in which folder he put it. In his computer there is a total of $$$N$$$ folders numbered from $$$1$$$ to $$$N$$$ and in only one of them he can find his favorite game. Fortunately, his friend Clippy promised to help.

Clippy offers Galdino the following game: you can choose two integers $$$L, R$$$ and I will tell you whether the game is in any of the folders in the interval $$$[L, R]$$$. However, you only have up to 25 tries and if you can't find your game until there, I will eat all of your files!

Feeling confident, Galdino decided to accept Clippy's risky game. Help him!

Input

The first line of input will contain a single integer $$$N$$$ ($$$1 \le N \le 10^6$$$) indicating the number of folders in Galdino's computer.

Output

When you feel that you found the right folder, print the string "! x", where $$$x$$$ is the index of the game's folder. After that, terminate your program.

Interaction

To ask Clippy a question, print two integers $$$L, R$$$ ($$$1 \le L \le R \le N$$$) and flush the output. After flushing it, the answer for this query can be read from input.

After every query, it will be printed to input 0 if the game can't be found in any folder in $$$[L, R]$$$ or 1 otherwise.

To flush you can use:

  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal;
  • see the documentation for other languages.
Examples
Input
1

1
Output
1 1

! 1
Input
4

0

0

1
Output
1 1

2 2

3 3

! 3