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
Ato know fan
Bbut does not guarantee that fan
- Willie is the only person at the party that everyone knows
You are only allowed to ask the question, "Does person
A knows person
The answer will be
1 if person
A knows person
0 if person
A does not know person
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
~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~
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
In order to submit an answer, print
! x, where
x is the number that Willie was assigned.
>>> denotes your output. Do not print
3 >>> ? 1 2 1 >>> ? 2 3 0 >>> ? 3 2 1 >>> ! 2