407937: GYM102946 D Discombobulator 3000

This is an interactive problem.

Diana the shark has built a new machine for her project: the Discombobulator 3000. It is capable of solving any interactive programming problem that involves a permutation!

One day, while Diana was swimming peacefully, the machine fell out of her pocket and landed on the ocean floor. Because of this, it broke into two pieces. Diana was not able to repair it immediately, but she knew how the machine works, even if it was broken:

• One piece of the machine contains a sequence $$$a_0, a_1, \dots, a_{n-1}$$$ of $$$n$$$ integers. The sequence is a permutation of the integers from 1 to $$$n$$$. That is, each integer between 1 and $$$n$$$ (inclusive) appears in this sequence exactly once.
• The other piece of the machine contains a sequence $$$b_0, b_1, \dots, b_{n-1}$$$ of $$$n$$$ integers. The sequence is also a permutation of the integers from 1 to $$$n$$$.
• There is an integer $$$k$$$ such that $$$0 \le k \le n - 1$$$ and the relation $$$a_i=b_{(i+k)\;\operatorname{mod}\;n}$$$ holds for $$$i=0,1,\dots,n-1$$$.

Unfortunately, Diana only knew the integer $$$n$$$, and had no knowledge about $$$k$$$ or the sequences. The only way to access the sequences is via a special button on the machine. When you press the button, the machine will ask you for two integers $$$x$$$ and $$$y$$$ and reply with the value $$$\max(a_x, b_y)$$$. The button cannot be pressed for more than $$$2n$$$ times in total, otherwise everything will explode.

Diana was discombobulated by the situation, and now she needs your help. If you can find out the integer $$$k$$$, then she will be able to combine the two pieces back into the Discombobulator 3000. Can you do that by interacting with the machine?

The first line of input contains the integer $$$n$$$.

The input has $$$q$$$ more lines if you press the button $$$q$$$ times. Each of these lines contains an integer - the number that the machine replies with.

Technical specification:

• $$$2 \le n \le 200$$$
• $$$0 \le k \le n - 1$$$

Your output should consist of $$$q+1$$$ lines if you press the button $$$q$$$ times.

Each time you wish to press the button, print a line in the form "? $$$x$$$ $$$y$$$", where $$$x$$$ and $$$y$$$ are the numbers you tell the machine. The machine's reply will be sent as one line of input (described above). Don't forget to flush the output stream after printing a line.

The last line should be in the form "! $$$k$$$", where $$$k$$$ is the integer you have to find.

Your output must satisfy $$$0 \le q \le 2n$$$ and $$$0 \le x, y \le n - 1$$$ in each line.

4
1
2
2
4
2

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

In the example, the sequences are $$$a = [2,3,1,4]$$$ and $$$b = [4,2,3,1]$$$. The answer is $$$k=1$$$.

Remember that you don't have to find the two sequences, only the integer $$$k$$$.