G. OMORI
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
.......................................
— Omori, OMORI

OMORI is bored in white space; he has been living there for as long as he can remember... He creates a game out of boredom with his dolls.

There are $$$n$$$ dolls in the possession of OMORI, exactly one of these dolls resembles OMORI (has no emotion); the other $$$n-1$$$ dolls can be of three types:

  1. Happy dolls (These dolls resemble Kel).
  2. Angry dolls (These dolls resemble Aubrey).
  3. Sad dolls (These dolls resemble Hero).
It is guaranteed that there is at least one doll of each type.

How does the game work? Since OMORI has been living alone for a lot of time, he started to make imaginary fights with dolls; he decides the winner according to the following chart:

Happy beats Angry - Angry beats Sad - Sad beats Happy

So, when two dolls fight, OMORI decides the result according to the following rules:

  1. If one of the two dolls is emotionless, the result is a tie.
  2. Otherwise, if the two dolls are of the same emotion, the result is a tie.
  3. Otherwise, decide the winner of the two dolls based on the emotion chart described above.

After explaining, OMORI then plays the game with you; the game is as follows: OMORI shuffles the $$$n$$$ dolls and asks you to find the emotionless doll (the one that resembles OMORI). You can do up to $$$3n$$$ questions of the form i,j, $$$(1 \le i,j \le n)$$$, and OMORI will answer with either $$$0$$$ or $$$1$$$.

When you ask OMORI about two dolls i,j, he will return $$$1$$$ only if doll $$$i$$$ beats doll $$$j$$$ in a fight; otherwise, he will return $$$0$$$ (whether it was a tie or doll $$$j$$$ won).

Input

The first line of input contains a single integer $$$n$$$ $$$(4 \le n \le 20000)$$$ — the number of dolls OMORI has.

The description of the interaction follows.

Interaction

To ask OMORI a question, you can output no more than $$$3n$$$ queries of the following format:

  • "? i j", where $$$i,j$$$ are two integers satisfying $$$(1 \le i,j \le n)$$$.

In response to this query, you will receive $$$1$$$ if doll $$$i$$$ beats doll $$$j$$$ in a fight, and $$$0$$$ otherwise.

Once you have found the answer, output a query of the following format:

  • "! x", where $$$x$$$ is the index of the emotionless doll.

If you make an invalid query, you will receive $$$−1$$$ instead of a response from OMORI. If you exceed the limit of $$$3n$$$ questions, you will receive $$$−2$$$ instead of a response from OMORI. If you return an incorrect answer, you will receive $$$−3$$$ instead of a response from OMORI. In all of these cases you will get the verdict Wrong answer. In this case, your program should terminate immediately to avoid undefined verdicts.

After outputting the queries/answer, do not forget to output a newline character and flush the output buffer. Otherwise, you will receive the verdict Solution "hung" (Idleness limit exceeded). To flush the buffer, use:

  • fflush(stdout) or cout.flush() in C/C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • refer to the documentation for other languages.
Examples
Input
4

1

0

0

0

0

1
Output

? 1 2

? 1 3

? 1 4

? 3 2

? 4 2

? 3 1

! 4
Input
4

0

0

0
Output

? 1 2

? 1 3

? 1 4

! 1
Note

In the first sample, the emotions of the dolls in order are: {"Happy", "Angry", "Sad", "Emotionless"}.

In the second sample, the emotions of the dolls in order are: {"Emotionless", "Happy", "Angry", "Sad"}.

OMORI spending time in white space thinking about a game