CF1019B The hat

这是一个交互题。 Imur Ishakov 决定组织一个喜欢玩著名游戏“帽子”的俱乐部。俱乐部有 $n$ 名学生参加，其中 $n$ 是偶数。Imur 让他们围成一圈，并通过抽签将学生分成若干对，但过程中出现了一些问题。参与者被编号为 $1$ 到 $n$，其中第 $i$ 位和第 $i+1$ 位（$1 \leq i \leq n-1$）是相邻的，第 $n$ 位和第 $1$ 位也是相邻的。每个学生都拿到了一张写有数字的纸条，保证每对相邻学生纸条上的数字恰好相差 $1$。原计划是让数字相同的学生配对，但实际上并不是所有数字都恰好出现两次。 众所周知，最方便的交流方式是让搭档正好坐在对面。编号为 $i$ 和编号为 $i+\frac{n}{2}$ 的学生正好坐在对面。Imur 想知道是否存在一对正好坐在对面的学生，他们拿到的数字是相同的。如果存在，请帮他找出这样的一对。 你可以询问“第 $i$ 位学生拿到的数字是多少？”，目标是在不超过 $60$ 次提问内判断是否存在这样的一对。

首先输入一个偶数 $n$（$2 \leq n \leq 100000$），表示学生总数。 你最多可以询问 $60$ 次。

每次询问第 $i$ 位学生的数字时，请输出「? $i$」，然后从标准输出读取第 $i$ 位学生拿到的数字 $a_i$（$-10^9 \leq a_i \leq 10^9$）。 当你找到满足条件的学生对时，请输出「! $i$」，其中 $i$ 是这对学生中的任意一个编号（$1 \leq i \leq n$）。如果确定不存在这样的对，请输出「! -1」。无论哪种情况，输出后都应立即终止程序。 你输出答案的那一条指令不计入 $60$ 次提问的限制。 每次输出后请务必刷新输出缓冲区。例如，C++ 使用 fflush(stdout)，Java 使用 System.out.flush()，Pascal 使用 flush(output)，Python 使用 sys.stdout.flush()。

输入输出样例展示了交互过程。 第一个样例的数字序列为 $1,2,1,2,3,4,3,2$。 第二个样例的数字序列为 $1,2,3,2,1,0$。 由 ChatGPT 4.1 翻译