题目描述

这是一个交互式问题。

某赛站的椅子在承受了超过非负整数 $k$ 的重量后会坏掉。但是你不知道 $k$ 的值，只知道正整数 $n$，且满足 $0 \le k \le n$。

现在你有两个完全相同的椅子，你可以在这两个椅子上进行测试。你可以在每个椅子上放置任意重量的物品。

你可以进行最多 $\lceil \sqrt{2n} + 5 \rceil$ 次询问，每次询问给出一个重量 $x$，并得到在这个重量下椅子是否会坏掉，需要注意的是，没坏掉的椅子可以继续用于询问，但如果某个椅子坏掉后，你就不能再在这个椅子上放置物品了。如果两个椅子都坏掉，你将无法继续询问。

请设计一种方案找到 $k$ 的精确值。准确地说，你需要在不多于 $\lceil \sqrt{2n} + 5 \rceil$ 次询问之后，输出一个整数 $x$，满足 $0 \le x \le n$，使得 $x$ 不会坏掉，但 $x+1$ 会坏掉。

$\lceil x \rceil$ 表示对 $x$ 向上取整。

输入格式

交互

开始时，首先读取一个整数 $n$ ($1 \leq n \leq 10^9$)，表示 $k$ 的上界。接下来，你将开始猜测 $k$。

在猜测过程中，你可以进行最多 $\lceil \sqrt{2n} + 5 \rceil$ 次查询，每次查询的格式为：

• ? x，其中 $x$ 是一个满足 $0 \leq x \leq n$ 的整数。

对于每次查询，将返回以下响应之一：

• 如果 $x \leq k$，返回 0，表示椅子没有坏掉；
• 如果 $x > k$，返回 1，表示椅子坏掉了。

当你确定了 $k$ 的值后，输出以下格式的答案：

• ! x，其中 $x$ 是你猜测 $k$ 的值 ($0 \leq x \leq n$)。

然后，程序应退出。

注意：

• 如果你的查询次数超过了 $\sqrt{2n} + 5$ 或者提交了不正确的答案，将会返回 -1 并视为答案错误，此时程序应立即终止，以避免不必要的后果。
• 仅有两个椅子，也就是说一旦返回的响应中累计达到两个 1，之后的任何查询都将返回 -1并视为答案错误

每次输出查询或答案后，记得输出换行符并刷新输出缓冲区。否则，可能会导致程序被判定为运行时间超限。可以使用以下方法刷新缓冲区：

• 在 C++ 中使用 fflush(stdout) 或 cout.flush()；
• 在 Java 中使用 System.out.flush()；
• 在 Pascal 中使用 flush(output)；
• 在 Python 中使用 stdout.flush()；
• 其他语言请参考相应的文档。

输出格式

样例 #1

样例输入 #1

10

1

0

0

0

1

样例输出 #1

? 5

? 1

? 2

? 3

? 4

! 3

提示

对于 $25 \%$ 的数据，交互库并不是自适应性的，即 $k$ 是预先确定的。

对于 剩下的 $75 \%$ 的数据，交互库是自适应性的，也就是实际的交互库刚开始并没有一个确定的答案，而是会随着交互过程确定一个符合题意的值。