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

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

​在游戏开始前，你拥有 个硬币；

​在开始猜测前，你需要支付 块的硬币以购买一个具有 面的骰子， 要求 。每次投掷该骰子，您将获得一个范围在的随机数，确保随机数服从均匀分布；

​每次猜测时，你需要指定一个正整数 （）。程序将帮助你投掷骰子，倘若你获得随机数 ，那么程序将会返回子数组 的最大值。每次猜测都会消耗个硬币。每次猜测过后，程序将随机调整数组的元素位置 ；

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

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

交互

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

"! m"

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

"? index"

表示你指定的下标索引， 注意要求 . 此时会输入一个正整数 ， 表示子数组 的最大值， 表示程序生成的随机数.

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

"! ans"

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

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

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

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

在 Java 中 System.out.flush()

在 Pascal 中 flush(output)

在 Python 中 stdout.flush()

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

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

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

输入 #1

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

输出 #1

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

​ 隐藏的数组， 第一次操作程序生成的随机数 ， 返回子数组 的最大值为 .

输入 #2

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

输出 #2

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

​ 隐藏的数组 ，第一次操作程序生成的随机数 ，返回子数组 的最大值 ；在第一次操作后，隐藏数组调整元素的位置，新的隐藏数组 。第二次操作程序生成的随机数 ，返回子数组 的最大值

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

​ 确保 ， 允许 数组元素出现重复.