简述题意

• 交互库内有一个长度为 $n$ 的 $01$ 串 $S=S_1S_2S_3\ldots S_n$，其中 $S_1=0$，$S_n=1$。

• 最多询问交互库 $20$ 个问题，每次询问一个数 $x$，交互库返回 $S_x$ 的值。

• 目标寻找到一个数 $id$ ，使得 $S_{id}\neq S_{id+1}$。

• $1\leq n \leq 2e5$。

交互格式

具体地，交互库会先给出一个数 $n$。

若询问交互库 $S_x$ 的值，应当以 $\verb|? x|$ 的格式进行询问，交互库会给出 $S_x$ 的值。

若给出答案 $id$，应当以 $\verb|! id|$ 的格式给出答案，若 $S_{id}\neq S_{id+1}$ 则获得该测试点分数。你不应该在此之后输出任何字符。

Translated by yujinning。