You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

本题为交互题，请确保你已经完成了交互题测试或了解交互题怎么做，监考人员不会回答任何关于如何做交互题的问题。

​你准备玩一个猜数字游戏，给定一个 $n$ 长的正整数数组$a$，数组$a$的元素对用户隐藏，你需要猜出$a$的最大值，猜测规则如下：

​在游戏开始前，你拥有 $C = min(8 * n, 13000)$ 个硬币；

​在开始猜测前，你需要支付 $m ^ 2$ 块的硬币以购买一个具有 $m$ 面的骰子， 要求 $1 \le m \le \lfloor \sqrt{C} \rfloor$。每次投掷该骰子，您将获得一个范围在$[1, m]$的随机数，确保随机数服从均匀分布；

​每次猜测时，你需要指定一个正整数 $i$ （$1 \le i \le n$）。程序将帮助你投掷骰子，倘若你获得随机数 $x$，那么程序将会返回子数组 $a[i : min(i + x - 1, n)]$ 的最大值。每次猜测都会消耗$\lfloor \sqrt{m} \rfloor$个硬币。每次猜测过后，程序将随机调整数组$a$的元素位置 ；

​当你的硬币数量小于 $\sqrt{m}$时，你不允许再次猜测，并输出你猜测到的数组$a$的最大值。此外，你允许随时输出猜测到的最大值！当你猜测到的最大值与 $a$ 的最大值相同时，你将获得游戏的胜利！

Input Format

第一行输入一个正整数 $n$， 表示隐藏数组 $a$ 的长度.

交互

要购买购买一个具有 $m$ 面的骰子，按照如下格式输出一行（不包含引号）

"! m"

要进行猜测，请按照如下格式输出一行（不包含引号）

"? index"

$index$ 表示你指定的下标索引， 注意要求 $1 \le index \le n$. 此时会输入一个正整数 $max$， 表示子数组 $a[i : min(i + x - 1, n)]$ 的最大值，$x$ 表示程序生成的随机数.

要输出答案，请按照如下格式输出一行（不包括引号）

"! ans"

$ans$ 表示你猜到的数组的元素最大值.

若在任何时候输入的数为-1,说明你的询问超出次数/询问不合法/回答不合法/答案错误/其他输入错误，此时，你需要直接退出程序，接收到Wrong Answer。否则，你可能会得到任意一种错误类型作为回应

输出询问或回答后，不要忘记输出换行并刷新缓存区。否则，您可能会收到 Time limit exceeded 判定。为此，请使用：

在 C++ 中 fflush(stdout)或 cout.flush()

在 Java 中 System.out.flush()

在 Pascal 中 flush(output)

在 Python 中 stdout.flush()

对于其他语言，请参阅其他语言的文档。

交互器是自适应的，在每一次猜测操作后，交互器都会重新调整隐藏数组 $a$ 的元素位置。

Output Format

Sample

// 后面的内容仅代表解释

输入 #1

4	//	隐藏数组的长度
5	//	第一次回答

输出 #1

! 4		//	购买一个具有 4 面的骰子
? 1		//	第一次操作，指定索引为1.
! 5		//	答案正确

​ 隐藏的数组$a = [1, 3, 2, 5]$， 第一次操作程序生成的随机数 $x = 4$， 返回子数组 $a[1 : 4]$ 的最大值$max$为 $5$.

输入 #2

5 	//	隐藏数组的长度
2	//	第一次回答
6	//	第二次回答

输出 #2

! 2		//	购买一个具有 2 面的骰子
? 1		//	第一次操作，指定索引为1
? 2		//	第二次操作，指定索引为2
! 6		//	答案正确

​ 隐藏的数组 $a = [1, 2, 3, 4, 6]$，第一次操作程序生成的随机数 $x = 2$，返回子数组 $a[1 : 2]$ 的最大值 $max = 2$；在第一次操作后，隐藏数组调整元素的位置，新的隐藏数组 $a = [4, 6, 1, 3, 2]$。第二次操作程序生成的随机数 $x = 1$，返回子数组 $a[2 : 2]$ 的最大值 $max = 6$

​ 注意，上述操作并非代表最优操作，仅仅作为操作的演示。

Hint

​ 确保 $1 \le n \le 10 ^ 4, 1 \le a_{i} \le 10^9$， 允许 数组元素出现重复.