问题描述

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

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

给定字符串的长度 $N$，但不给出字符串 $S$ 的具体内容。相反，你可以最多向评测系统提问 $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$

如果有多个解，你可以任意输出其中之一。

注意事项

• 每个消息结束时，请换行并刷新标准输出。否则，可能会超时。