题意解析

Linda 想要确定一个“关键颜色差” $C$，当且仅当相邻两次染色的颜色编号差的绝对值 $\ge C$ 时，Archie 才会注意到变化。

她拥有编号 $1$ 到 $N$ 的 $N$ 种发色，每种只能用一次。
第一次染发的反应（与实验前发色相比）无意义。
从第二次染色开始，交互器会根据相邻两个颜色的 $|{\rm new} - {\rm prev}|$ 是否 $\ge C$ 返回 $1$（注意到）或 $0$（未注意到）。

目标：在最多 $64$ 次询问内确定 $C$ 的值。
$N$ 可大到 $10^{18}$，$T$ 最多 $1200$ 组。

关键观察

1. 第一个询问的返回值是无效的，但我们必须先输出一个颜色才能开始交互，这个返回值可忽略。
2. 从第二次询问开始，返回值取决于当前颜色与上一个颜色的差的绝对值 $\Delta$：
   • 如果 $\Delta \ge C$，返回 $1$；
   • 如果 $\Delta < C$，返回 $0$。
3. 每种颜色只能用一次，因此我们选择的颜色序列是 $1$ 到 $N$ 的一个排列。

问题转换

如果我们知道相邻两次颜色的差 $\Delta$ 以及返回值 $r$，就可以得到关于 $C$ 的信息：

• 如果 $r = 1$，则 $C \le \Delta$；
• 如果 $r = 0$，则 $C > \Delta$。

换句话说，每次有效的询问（从第二个颜色开始）都可以得到一个形如 $C \le \Delta$ 或 $C > \Delta$ 的条件。

解题思路

我们可以将 $C$ 的可能值区间初始设为 $[1, N]$（实际上 $C$ 的取值范围是 $1$ 到 $N$，但注意 $C$ 可以等于 $N$，此时只有相邻颜色差 $\ge N$ 才会被注意到，而相邻颜色差最大为 $N-1$，所以除了第一次无效外，后面所有有效询问返回值都是 $0$）。

考虑用二分法确定 $C$ 的值：

我们需要构造相邻颜色的差 $\Delta$ 来测试 $C$ 是否小于等于某个值 $m$。

假设上一个颜色是 $prev$，当前颜色是 $now$，则 $\Delta = |now - prev|$。如果我们想让 $\Delta$ 恰好等于某个我们想要测试的值 $d$，就必须选择 $now = prev \pm d$，且 $1 \le now \le N$ 且 $now$ 未被使用过。

为了用二分法，我们需要测试 $C \le m$ 是否成立。
如果存在一个 $d \ge m$ 且相邻染色时返回 $1$，则说明 $C \le d$ 成立，进而 $C \le m$ 成立（因为 $m \le d$）。
如果我们用 $d = m$ 测试并且返回 $0$，则 $C > m$。

但是，直接测试 $d = m$ 可能不方便，因为每次选择的颜色必须未使用过，且 $|now - prev| = m$ 不一定可行（可能 now 已被使用或越界）。

构造序列的策略

一个经典构造是：从颜色 $1$ 开始，然后跳到 $1 + m$，再跳到 $(1 + m) - (m-1) = 2$，再跳到 $2 + m$，再跳到 $3$，如此往复。
这样相邻差值在 $m$ 和 $m-1$ 之间交替。

• 如果 $C \le m$，则差值为 $m$ 时会返回 $1$，差值为 $m-1$ 时会返回 $1$ 或 $0$ 取决于 $C$ 和 $m-1$ 的关系，但至少 $m$ 的这一步能测出 $C \le m$。
• 如果 $C > m$，则差值为 $m$ 时也会返回 $0$。

所以通过一次 $m$ 的差值测试，就能二分。

算法步骤

1. 初始化 $l = 1, r = N$，$C$ 的可能范围。
2. 选择一个起始颜色 $start$（比如 $1$），输出第一个询问（返回值忽略）。
3. 当 $l < r$ 时：
   • 计算 $mid = \lfloor (l + r) / 2 \rfloor$。
   • 构造相邻差值 $mid$ 的染色，即从当前颜色 $p$ 选择 $p+mid$ 或 $p-mid$ 中一个合法且未用过的颜色。
   • 输出这个颜色，得到返回值 $resp$（从第二次开始有效）。
   • 如果 $resp = 1$，则 $C \le mid$，令 $r = mid$。
   • 如果 $resp = 0$，则 $C > mid$，令 $l = mid + 1$。
4. 最终 $l = r = C$，输出答案。

询问次数分析

每次二分将区间长度减半，区间长度从 $N$ 降到 $1$ 需要 $\lceil \log_2 N \rceil$ 次有效询问。
加上第一次无效询问，总询问次数为 $\lceil \log_2 N \rceil + 1$。
当 $N \le 10^{18}$ 时，$\log_2 N \le 60$，因此最多 $61$ 次询问，满足 $64$ 次限制。

注意事项

• 每次选择的颜色必须未使用过，且范围在 $[1, N]$ 内。构造差值时需确保合法。
• 第一次询问的返回值无意义，但必须有一个“上一个颜色”才能开始有效比较，所以要先随便问一个颜色。
• 每次输出后刷新缓冲区。
• 多组数据，每组独立。

示例流程（与题目样例一致）

样例中 $N=7$，$C=4$：

1. 问颜色 2（返回 1 但无效）。
2. 问颜色 7，与 2 的差为 5，返回 1 → $C \le 5$。
3. 问颜色 4，与 7 的差为 3，返回 0 → $C > 3$。
4. 问颜色 1，与 4 的差为 3，返回 0 → $C > 3$（同条件）。
5. 问颜色 5，与 1 的差为 4，返回 1 → $C \le 4$。 结合 $C > 3$ 且 $C \le 4$ → $C=4$。

总结

本题是一个交互题，核心是通过构造相邻颜色差来二分查找 $C$，利用返回值的比较结果不断缩小区间，直到确定 $C$ 的精确值。
关键在于构造颜色序列，使得每次测试的差值可控，并且所有颜色不重复使用。
询问次数控制在 $O(\log N)$ 内，足以应对 $N$ 极大的情况。