通过询问查找

题目描述

这是一个交互式任务(你的程序通过输入输出与评测程序交互)。

评测程序持有一个由 $0$ 和 $1$ 组成、长度为 $N$ 的字符串 $S = S_1S_2\ldots S_N$。 其中,$S_1 = 0$,$S_N = 1$。

你只知道 $S$ 的长度 $N$,不知道 $S$ 的内容。 作为代替,你可以按如下方式向评测程序提问最多 $20$ 次:

选择满足 $1 \le i \le N$ 的整数 $i$,询问 $S_i$ 的值。

输出一个满足 $1 \le p \le N-1$ 且 $S_p \neq S_{p+1}$ 的整数 $p$。

在本问题的设定下,可以证明这样的 $p$ 必然存在。

输入格式

这是一个交互式任务(你的程序通过输入输出与评测程序交互)。

首先,从标准输入读取字符串 $S$ 的长度 $N$:

$N$

然后,你可以按题目描述向评测程序提问最多 $20$ 次。

输出格式

每次提问按以下格式输出到标准输出,其中 $i$ 是满足 $1 \le i \le N$ 的整数:

$?$ $i$

作为回答,评测程序将从标准输入按以下格式给出 $S_i$ 的值:

$S_i$

这里,$S_i$ 为 $0$ 或 $1$。

当你找到满足题目条件的整数 $p$ 时,按以下格式输出,并立即终止程序:

$!$ $p$

如果存在多个解,可以输出任意一个。

样例

本题为交互式任务,没有样例。

数据范围

• $2 \le N \le 2 \times 10^5$

提示

每次输出后都要换行并刷新标准输出(flush)。否则可能会超时(TLE)。

答案不唯一,输出任意合法解即可。