当前没有测试数据。

D - 查询解答

得分: $400$ 分

题目描述

这是一个交互式任务，您的程序与评测系统通过标准输入和输出进行交互。

评测系统有一个长度为 $N$ 的字符串，由 $0$ 和 $1$ 组成：$S = S_1S_2\ldots S_N$。 其中 $S_1 = 0$，$S_N = 1$。

给定字符串 $S$ 的长度 $N$，但不知道具体的内容。 您最多可以向评测系统询问 $20$ 个问题，询问的方式如下：

• 选取一个整数 $i$，满足 $1 \leq i \leq N$，并询问 $S_i$ 的值。

输出一个整数 $p$，满足 $1 \leq p \leq N-1$ 且 $S_p \neq S_{p+1}$。
可以证明，在本问题的设置下，总是存在这样的 $p$。

约束条件

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

输入和输出

首先，从标准输入中读入字符串 $S$ 的长度 $N$：

$N$

然后，您可以按照问题描述中的方式向评测系统提问最多 $20$ 次。

按照以下格式将每一个问题输出到标准输出中，其中 $i$ 是一个满足 $1 \leq i \leq N$ 的整数：

``` ? $i$ ```

评测系统将以以下格式从标准输入中给出 $S_i$ 的值作为回答：

``` $S_i$ ```

其中 $S_i$ 的值为 $0$ 或 $1$。

当找到满足题目条件的整数 $p$ 时，以以下格式输出，然后立即退出程序：

``` ! $p$ ```

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

备注