破解对撞机

时间限制：1 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

这是一道交互题。

迈尔斯继续与“Alchemax”斗争。这次的任务是破解对撞机的设置，以阻止其再次启动。

对撞机共有 $n$ 个设置 $a_i$，编号从 $1$ 到 $n$，每个设置都是正整数。公司对外人设置了保护，因此不能直接得知某个设置的值。但是任何人都可以查询某个 $f(x)$，其值等于编号从 $x$ 向前循环移位 $c$ 个位置（$0 \le c \le n-1$）的设置，即当 $x + c \le n$ 时等于 $a_{x+c}$，否则等于 $a_{x+c-n+1}$。

迈尔斯发现这些设置实际上是严格递增的，即所有 $i$ 从 $1$ 到 $n-1$ 满足 $a_{i+1} > a_i$。现在，为了阻止对撞机，迈尔斯必须找出只有“Alchemax”员工知道的数字 $c$——设置访问系统中使用的移位值。

请根据给定的 $n$ 和最多 $42$ 次 $f(x)$ 查询机会，求出 $c$ 的值。

输入格式

第一行包含一个整数 $n$ ——设置的数量（$1 \le n \le 10^5$）。
保证所有 $a_i$ 均为 $1$ 到 $10^9$ 之间的整数。

交互格式

交互过程由你的程序向交互器发起查询，交互器给出回答。

你可以查询 $f(x)$ 最多 $42$ 次，其中 $1 \le x \le n$。要查询值，请输出一行 ? x（将 $x$ 替换为实际数字）。如果尚未超出 $42$ 次 ? 查询限制，下一行交互器会输出一个整数 $f(x)$，其值为 $a_{x+c}$（当 $x+c \le n$）或 $a_{x+c-n+1}$（否则）。

要输出答案，请打印一行 ! c（$0 \le c \le n-1$）。输出答案不计入查询次数。输出答案后，程序应立即以返回码 0 结束。

如果程序在某时刻超过 $42$ 次查询，交互器将在下一行输出 $-1$ 并以 WA（Wrong Answer）结束。为避免得到 RE、TL 或 IL 判定，程序在读到 $-1$ 后应立即以返回码 0 结束。

每次查询后请务必刷新输出缓冲区，以便交互器接收到你的查询。在 C++ 中使用 std::cout.flush()，在 Java 中使用 System.out.flush()，在 Python 中使用 sys.stdout.flush()，其他语言类似。如果不刷新缓冲区，程序可能会得到 TL 或 IL 判定。

样例

样例 1

输入：

5

4

5

1

输出：

? 1

? 2

? 3

! 3

样例 2

输入：

5

4

3

2

1

输出：

? 4

? 3

? 2

? 1

! 0