Linda 喜欢不时地改变她的发色，如果她的男朋友 Archie 能注意到新旧发色之间的差异，她会很高兴。Archie 仅在注意到差异时才会对 Linda 的发色发表评论——因此 Linda 总能知道 Archie 是否察觉到了这种差异。
市场上有一种新的染发剂系列，所有可用的颜色都用从 $1$ 到 $N$ 的整数编号，编号的数值差异越小，视觉上的差异也越小。
Linda 假设对于这个系列，存在一个临界颜色差异 $C$ ($1 \le C \le N$)，使得如果 $|color_{\text{new}} - color_{\text{prev}}| \ge C$，Archie 就会注意到当前颜色 $color_{\text{new}}$ 与之前颜色 $color_{\text{prev}}$ 之间的差异；如果 $|color_{\text{new}} - color_{\text{prev}}| < C$，则不会注意到。
现在她购买了该系列 $N$ 套染发剂——每种颜色（从 $1$ 到 $N$）各一套，并准备进行实验。Linda 将定期更换发色，并观察 Archie 的反应——他是否注意到了颜色变化。由于每套染发剂都应完整使用，因此每种发色最多只能使用一次。
实验开始前，Linda 使用的是另一种与该系列不兼容的染发剂，因此为了实验的清晰度，Archie 对第一次使用的颜色的反应是没有意义的。
她的目标是在有限次数的染色中找到 $C$ 的精确值。请编写一个程序，通过使用给定的 $N$ 种颜色进行实验并观察 Archie 对颜色变化的反应来找出 $C$ 的值。
交互
这是一个交互式任务。输入开始时包含一个整数——$N$ 的值 ($1 < N \le 10^{18}$)。$C$ 的值由评测系统保密。
然后，你的程序应按以下格式输出查询：“? P”，其中 $P$ 是一个整数 ($1 \le P \le N$)，表示下一次使用的颜色。对于每次查询，评测系统会在输入的下一行给出答案。如果 Archie 注意到了最后两种颜色之间的差异，答案为 $1$，否则为 $0$。任意两次查询的 $P$ 值不得相同。
当你的程序确定了 $C$ 后，应按以下格式输出其值：“= C”并终止执行。评测系统不会对该输出做出响应，也不会接受后续查询。
说明
为了在你的程序和评测系统之间建立正确的通信，你应该在每次查询后刷新输出流（表 1）。
| 语言 | 命令 |
|---|---|
| C++ | std::cout << std::endl; |
| Java | System.out.flush(); |
| Python | sys.stdout.flush() |
表 1：刷新命令
如果在通信过程中违反了任务约束，即使打印了正确的答案，也可能收到“Output isn’t correct”的结果。违反通信协议本身可能会导致“Execution killed”的结果。
提交用户测试需要指定一个包含测试用例参数的输入文件。输入文件的格式为单行“N C”。
样例
| 输入 | 输出 | 说明 |
|---|---|---|
| 7 | $N = 7$ | |
| ? 2 | ||
| 1 | 第一次查询的答案没有意义（也可以是 0） | |
| ? 7 | ||
| 1 | $C \le 5$ | |
| ? 4 | ||
| 0 | $3 < C \le 5$ | |
| ? 1 | ||
| 0 | $3 < C \le 5$ | |
| ? 5 | ||
| 1 | $3 < C \le 4$。因此，$C = 4$。 | |
| = 4 |
注：检查差异 4 是明智的。然而，这在下一次查询中无法完成，因为 $4 + 4 = 8$ 和 $4 - 4 = 0$ 均超出了允许的区间 $1 \le P \le 7$。
子任务
你的程序最多可以使用 $64$ 次“?”查询来找到 $C$ 的正确值。
- (9 分) $N \le 64$
- (13 分) $N \le 125$
- (21 分) $N \le 1000$
- (24 分) $N \le 10^9$
- (33 分) 无其他约束