D. Snakes Among Us
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem!

There are $$$n$$$ ($$$n$$$ is odd) students in your class indexed from $$$1$$$ to $$$n$$$, each with marks between $$$-10^9$$$ and $$$10^9$$$ (excluding $$$0$$$). You can ask the marks of the $$$j^{th}$$$ student to the $$$i^{th}$$$ the student($$$i$$$ $$$\ne$$$ $$$j$$$), if the marks of the $$$i^{th}$$$ student is positive, then he will always truthfully reply the correct marks of the $$$j^{th}$$$ student else he may flip the sign of the marks. You know that the median of the class is positive and you want to find the student with the maximum marks in no more than $$$\dfrac{3(n+1)}{2}$$$ queries.

The query should be of the form: $$$?$$$ $$$i$$$ $$$j$$$ ($$$i$$$ $$$\ne$$$ $$$j$$$). The answer will be:

  • a single integer $$$x$$$, the marks of the $$$j^{th}$$$ student given by $$$i^{th}$$$ student.

It is given that there exists a unique student with maximum marks.

Input

The first line contains a single odd integer $$$n$$$ ($$$3 \le n \le 10^3$$$) — the number of students.

Interaction

The interaction between your program and the jury's program begins after reading the number of students $$$n$$$.

To make a query, output a line in the format "? i j", where $$$i \ne j$$$.

As an answer, you will receive a non-zero integer $$$x$$$ ($$$-10^9 \le x \le 10^9$$$), the marks of the $$$j^{th}$$$ student given by $$$i^{th}$$$ student.

You can make no more than $$$\dfrac{3(n+1)}{2}$$$ queries. To output the answer you need to print "! i", where $$$i$$$ is the student with maximum marks. Outputting the answer does not count as a query.

The interactor in this problem is not adaptive.

You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Example
Input
5

2

-4

4
Output

? 1 2

? 5 4

? 5 4

! 4
Note

Marks of the $$$5$$$ people are $$$1, 2, 3, 4, -5$$$.

  1. In the first query, marks of person $$$2$$$ is asked to person $$$1$$$.

    They answer $$$2$$$, since 1 has to tell the truth.

  2. In the second query, marks of person $$$4$$$ is asked to person $$$5$$$.

    They answer $$$-4$$$, since 5 chose to lie.

  3. In the third query, marks of person $$$4$$$ is asked to person $$$5$$$.

    They answer $$$4$$$, since 5 chose not to lie.