Willie attends a party consisting of ~N~ people, including himself. Everyone at the party is assigned a number between ~1~ to ~N~ and no two people will be assigned the same number.

The following statements regarding the party are true,

• Everyone at the party knows Willie because everyone attending the party is part of Willie's Fan Club
• Willie does not know anyone at the party because he has too many fans
• Willie's fans occasionally hold gatherings, so it is possible for a fan A to know fan B but does not guarantee that fan B knows fan A
• Willie is the only person at the party that everyone knows

You are only allowed to ask the question, "Does person A know person B?".

The answer will be 1 if person A knows person B and 0 if person A does not know person B.

Can you determine which number Willie was assigned?

Each time you output, you may need to output a new line and flush your output buffers. For example, in Python you can do this with import sys; sys.stdout.flush(), in Java with System.out.flush() and in C++ with cout.flush() or fflush(stdout).

Constraints

~3 \le N \le 100\,000~

You are only allowed to ask ~N~ questions and submit one answer.

~A \neq B~

~1 \le x \le N~

Interaction

The first line of input will be ~N~.

Questions should printed in the form ? A B followed by a newline.

The next line of input will be either 1 or 0.

In order to submit an answer, print ! x, where x is the number that Willie was assigned.

Sample Interaction

>>> denotes your output. Do not print >>> out.

3
>>> ? 1 2
1
>>> ? 2 3
0
>>> ? 3 2
1
>>> ! 2