这是一个交互式问题。

Putata 有 $n$ 盏灯，从左到右编号为 $1$ 到 $n$。初始时，所有灯都是关闭的。其中一盏灯是他的最爱，这盏灯的编号是隐藏的。Budada 想知道 Putata 最喜欢的灯的编号，他可以进行以下查询：

• “? $x$”：如果编号为 $x$ 的灯是关闭的，则将其打开，并询问 Putata：Putata 最喜欢的灯左侧已打开的灯的数量减去右侧已打开的灯的数量的绝对值。请注意，你不能关闭灯。

Budada 最多只能进行 40 次查询。请帮助他找到 Putata 最喜欢的灯。

在本题中，交互器是自适应的，这意味着答案可能不是预先确定的，交互器可以任意选择答案，只要该答案与你的交互过程保持一致即可。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示灯的数量。

交互

你可以进行不超过 40 次查询。要进行查询，请在单独的一行输出 “? $x$” ($1 \le x \le n$)，然后从标准输入读取响应。

作为对查询的响应，交互器将输出 Putata 最喜欢的灯左侧已打开的灯的数量减去右侧已打开的灯的数量的绝对值。

要给出你的答案，请在单独的一行输出 “! $x$” ($1 \le x \le n$)，其中 $x$ 是 Putata 最喜欢的灯的编号。输出答案不计入 40 次查询的限制。

在此之后，你的程序应该终止。

在打印查询后，不要忘记输出换行并刷新缓冲区。为此，请在 C++ 中使用 fflush(stdout) 或 cout.flush()，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)，或在 Python 中使用 stdout.flush()。

样例

样例输入 1

3
1
2
2

样例输出 1

? 1
? 2
? 3
! 3