B. Opposite Friends
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There are $$$2N$$$ friends sitting around a circle, numbered from $$$1$$$ to $$$2N$$$ in clockwise order. For every $$$1 \le i \lt 2N$$$, friends $$$i$$$ and $$$i+1$$$ are adjacent, and friends $$$2N$$$ and $$$1$$$ are adjacent. For every $$$1 \le i \le N$$$, friends $$$i$$$ and $$$i+N$$$ sit opposite each other.

Friend $$$i$$$ has a hidden positive integer $$$a_i$$$. The hidden integers satisfy

$$$$$$|a_i-a_j|=1$$$$$$

for every pair of adjacent friends $$$i$$$ and $$$j$$$.

Your task is to find two opposite friends who have the same hidden integer, or determine that no such pair exists.

The hidden integers are fixed before the interaction starts and do not change in response to your queries.

Input

The first line contains one integer $$$N$$$ ($$$2 \le N \le 10^5$$$).

It is guaranteed that $$$1 \le a_i \le 10^9$$$ for every $$$1 \le i \le 2N$$$, and that the hidden integers satisfy all conditions from the statement.

Interaction

To learn the hidden integer of friend $$$i$$$ ($$$1 \le i \le 2N$$$), print

$$$$$$\mathtt{?\ i}$$$$$$

Then read one integer: the value of $$$a_i$$$.

You may make at most $$$40$$$ queries.

When you have found two opposite friends $$$i$$$ and $$$j$$$ with $$$a_i=a_j$$$, print

$$$$$$\mathtt{!\ i\ j}$$$$$$

You may print $$$i$$$ and $$$j$$$ in either order.

If no such pair exists, print

$$$$$$\mathtt{!\ -1\ -1}$$$$$$

The final answer does not count as a query. After printing the final answer, your program must terminate immediately.

After every query and after the final answer, print an end-of-line and flush the output buffer. Otherwise, you may receive the Idleness limit exceeded verdict.

If your program prints an invalid query, makes more than $$$40$$$ queries, or prints an incorrect final answer, it will receive a wrong answer verdict.

Example
Input
2

100

100
Output
? 1

? 3

! 1 3
Note

The sample shows one possible interaction. The values read after the two queries are both $$$100$$$, so friends $$$1$$$ and $$$3$$$ form a valid final answer. Empty lines are shown only to make the order of messages easier to read.

To flush the output buffer, use:

  • cout « endl in C++;
  • System.out.flush() in Java;
  • flush=True in Python.