Problem Statement

A programming contest hosted by Yukikoda Inc. was held. $N$ people numbered $1, 2, \ldots , N$ participated in the contest, and everyone received a distinct rank from $1$ st to $N$ th place.

You are a recruiter at Yukikoda Inc. and have decided to scout the person who placed $2$ nd, but since you do not yet know the results of the contest, you have decided to ask the participants questions.

The participants are all contrarians, so they will only answer questions of the following form.

• Between person $x$ and person $y$ ($x\neq y$), which one ranked higher?

Identify the number of the person who placed $2$ nd by asking at most $334$ questions of this form.

Input and Output

First, the number of participants $N$ ($2\leq N\leq 300$) is given from standard input as follows.

$N$

Then, your program can make up to $334$ question queries by writing to standard output in the following format.

? $x\ y$

This output means asking which of person $x$ and person $y$ ranked higher. $x$ and $y$ must be integers satisfying $1\leq x, y\leq N$, $x\neq y$.

After you make a question query, its answer is given from standard input in the following format.

$ans$

If person $x$ ranked higher (has a smaller rank number), then $ans=x$; otherwise, $ans=y$.

Finally, you must output your answer in the following format.

! $ans$

Your answer is judged correct if the number of the person who placed $2$ nd can be uniquely determined from the question queries made so far and that number equals $ans$.

Notes

• After each output, you must flush standard output.
• After each question query, be sure to read its result.
• After outputting your answer, your program must terminate immediately.
• In some test cases, the answers to question queries may change depending on the question queries made so far, but an answer will never contradict the question queries made so far.

Sample

4
4
2
1

? 1 4
? 2 4
? 1 3
! 4

4
1
2
2

? 1 3
? 2 4
? 1 2
! 4