[BalticOI 2020 Day1] 染色

Linda 喜欢时不时改变她头发的颜色，如果她的男友 Archie 注意到她头发颜色发生了改变，Linda 会十分高兴。当且仅当 Archie 发现 Linda 的头发颜色发生改变时，Archie 才会去评论 Linda 头发的新颜色。这意味着 Linda 始终可以知道 Archie 是否发现她的头发颜色有改变。 现在市场上有一个新染发剂系列，该染发剂系列有 $N$ 种颜色，从 $1$ 到 $N$ 编号。两个颜色的相近程度与它们编号的差值有关——差值越小，则越相近。 Linda 发现，对于该系列的染发剂，存在一个色差阈值 $C$（$1 \leq C \leq N$）。具体来说，假如 Linda 之前使用的染发剂颜色编号为 $color_{prew}$，Linda 接下来打算使用的染发剂颜色编号为 $color_{new}$，则 Archie 会注意到 Linda 的颜色头发差异，当且仅当 $\left | color_{new}-color_{prew}\right | \geq C$。 现在 Linda 买下了一套该系列的染发剂，准备做一个实验。她会不断地更换头发的颜色，并观察 Archie 是否注意到了头发颜色发生改变。因为染发剂有限，每种颜色的染发剂最多只能使用一次。 在实验开始之前，Linda 使用的是另外一个系列的染发剂，因此讨论第一次染发后 Archie 的反应是没有意义的。 现在 Linda 想要通过有限的时间找到阈值 $C$，请写一个程序帮助她完成这个任务。 ### 交互方式 本题是一道交互题。 **与原题不同的是，为了压缩数据组数，本题单个测试点中将包含多组数据。** ~~输入第一行包含一个整数 $T$，表示该测试点的数据组数。~~ 对于每组数据，你首先将读入一个整数 $N$，代表该系列染发剂的颜色数量。 接下来，你可以按如下形式输出来进行询问：`? P`。其中 $P$ 代表 Linda 下一次要使用的染发剂的颜色编号。你输出的 $P$ 需要满足 $1 \leq P \leq N$，且任意两次询问的 $P$ 均不相同。 在询问过后，你的程序将读入一个整数，若这个整数为 $1$，代表 Archie 注意到了 Linda 头发颜色的变化；若为 $0$，则表示他没有注意到颜色的变化。 当你确认了阙值 $C$ 后，按如下格式输出答案：`= C`。 如果答案正确，将会直接进入下一组数据的交互。 如果答案错误，交互器将直接终止你的程序。 对于每组测试数据，你的程序可以最多进行 $64$ 次询问（最后输出答案不算作询问）。 请注意，一般情况下程序的输出会存放在缓冲区中，为了确保你的输出能被交互库接收，请在输出一行之后刷新缓冲区。 - 对于 C++ 语言，可以使用 `std::cout<<std::endl` 来在输出换行的同时刷新缓冲区； - 对于 Java 语言，可以使用 `System.out.flush();` 来刷新缓冲区； - 对于 Python 语言，可以使用 `sys.stdout.flush()` 来刷新缓冲区。

1
7

1

1

0

0

1

? 2

? 7

? 4

? 1

? 5

= 4

### 样例解释 为了方便各位理解交互过程，部分行之间人为添加了空行。 下面依次解释每次询问过程： 1. 这一次询问的结果无意义。 2. 此次询问后有 $C \leq 5$； 3. 此次询问后有 $3 \lt C \leq 5$，这时候可以考虑检测差值为 $4$ 时的情况。但因为 $4+4=8$ 和 $4-4=0$ 都不合法，因此不再考虑这么做。 4. 此次询问后有 $3 \lt C \leq 5$。 5. 此次询问后有 $3 \lt C \leq 4$，即 $C=4$。 ### 子任务 所有数据均满足：$1 \leq T \leq 1200$，$1 < N \leq 10^{18}$。 - 子任务 1（9 分）：$N \leq 64$； - 子任务 2（13 分）：$N \leq 125$； - 子任务 3（21 分）：$N \leq 10^3$； - 子任务 4（24 分）：$N \leq 10^9$； - 子任务 5（33 分）：无特殊限制。