AT_kupc2024_l Long Street

本题为**交互式**题目，且**评测器为自适应（adaptive）**。详细内容请参见提示部分。 有 $N$ 个点，编号分别为 $1$ 到 $N$，这些点按顺序排列在数轴上。对于每个 $i$ 满足 $1\le i\le N-1$，点 $i$ 与点 $i+1$ 之间的距离为 $2^{P_i}$。$N$ 和 $P$ 由输入给出。 评测程序会隐藏一个 $1\le x\le N$，你可以进行以下操作来提问： - 选择一个整数 $i$，$1\le i\le N$，询问在所有 $N$ 个点中，第 $i$ 个点距离隐藏点 $x$ 的距离是第几近（按距离排序）。注意，距离排名为 $1$ 表示最近，例如 $i=x$ 时，排名为 $1$。 你需要在不超过 $\lfloor\log_2 N\rfloor$ 次提问内，确定 $x$ 的值。

本题为交互题。 首先，你需要从标准输入读取 $N$ 和 $P$。 > $N$ > $P_1\ P_2\ \dots\ P_{N-1}$ 接下来，重复提问直到能够唯一确定 $x$。每一次提问，请按下述格式输出到标准输出： > ? $i$ 这里 $i$ 必须满足 $1\le i\le N$。你会收到如下格式的评测器响应（通过标准输入读取）： > $r$ 这里 $r$ 是本次提问的答案。如果提问不合法，或提问次数超过 $\lfloor\log_2 N\rfloor$，则 $r$ 等于 `-1`。 如果收到 `-1`，说明你已经被判为不正确，此时请立即停止程序。 一旦你唯一确定了 $x$，请以如下格式输出你的答案： > ! $x$ 随后请立即退出程序。

无额外输入/输出格式要求，交互格式详见输入格式。

## 注意事项 - **每次输出后必须加上换行，并刷新输出缓冲区。** 如果没有这么做，你可能会被判为 TLE 或 WA。 - 输出答案或收到 `-1` 响应后，应立即结束程序。否则，评测结果不可预测。 - 不要输出多余的换行，否则会被视为输出格式不正确。 - **本题的评测器为自适应（adaptive）。** 也就是说，在任何时刻，只要不与已有提问结果矛盾，评测器会动态选择 $x$ 的值，详情见下方样例。 ## 输入输出样例 例如输入 $N=4, P=(2,1,3)$，初始时评测器假定 $x=2$。 输入 输出 说明 4 2 1 3 输入 $N,P$。 ? 4 提问 $i=4$。 4 回答为 $4$。 ? 1 提问 $i=1$。 3 回答为 $3$。 ! 2 输出你的答案 $x=2$。 事实上，评测器在你给出答案前，可以将 $x$ 从 $2$ 改为 $3$ 以保证和所有历史问答相符。因此可能即使回答正确也不一定被判对。 ## 数据范围 - $2\le N\le 2\times 10^5$ - $N$ 为整数 - $P$ 为 $1,2,\dots,N-1$ 的一个排列 由 ChatGPT 5 翻译