T531926 International Chairs-Problem Contest

**这是一个交互式问题。** 某赛站的椅子在承受了超过非负整数 $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()`； - 其他语言请参考相应的文档。

无

对于 $ 25 \% $ 的数据，交互器是静态的，即 $k$ 是预先确定的。 对于 剩下的 $ 75 \% $ 的数据，交互器是动态的，即 $k$ 会随着询问的进行而在满足题意的范围内变化。