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 翻译