题目背景

这是一道交互题。交互库自适应。请注意特殊的时间限制。

每次输出后请记得清空缓存

简化题意：$\texttt{Link}$。

题目描述

你需要猜一个正整数 $q$，保证 $q\in [1,n]$；

你每次可以用诸如 ? x y 的询问，交互库会在 $[x,y]$ 中指定选择一个数 $z$；

然后交互库会输出形如 u v 的回答，表示指定的数是 $u$，其与 $q$ 的关系为 $v$；

具体地，

• 当交互库返回的 $v=0$ 时，表示 $u<q$；
• 当交互库返回的 $v=1$ 时，表示 $u=q$；
• 当交互库返回的 $v=2$ 时，表示 $u>q$。

而一次询问的代价是 $\dfrac{1}{y-x+1}$；

你可以通过 ! x 输出你认为正确的答案。

现在你要求出 $q$。

---

设你的代价为 $x$，你每个测试点获得的分数和你的总代价有如下关系（每个测试点满分 $10$ 分）：

• 若 $x\le 1.9813035$，则你可以得到 $\text{10 pts}$；
• 若 $1.9813035 < x \le 12$，则你可以得到 $\lfloor(12-x)\times0.7 \div 1.00186965\rfloor \text{ pts}$。
• 若 $x\ge12$，则你可以得到 $\text{0 pts}$。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

交互格式

一开始交互库会给你 $n$，

然后你可以按题目描述中的方式进行询问或回答答案；

在回答后请立即退出程序。

输入格式

见交互格式。

输出格式

见交互格式。

2

1 0
 

? 1 2

! 2

3

1 0

3 2
 

? 1 3

? 3 3

! 2

提示

• 样例 $1$ 解释：

  询问后发现 $1<x\le2$，所以 $x=2$；

• 样例 $2$ 解释：

  第一次询问后发现 $1<x\le3$；

  第二次询问后发现 $1<x<3$，所以 $x=2$；

【数据规模与约定】

测试点编号	$n \le$	测试点编号	$n\le$
$\texttt{1}$	$1$	$\texttt{6}$	$2\times 10^3$
$\texttt{2}$	$7$	$\texttt{7}$	$10^4$
$\texttt{3}$	$20$	$\texttt{8}$	$5\times 10^4$
$\texttt{4}$	$80$	$\texttt{9}$	$10^5$
$\texttt{5}$	$300$	$\texttt{10}$

对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le q,\forall u\le n$，$\forall v\in\{0,1,2\}$。

保证每询问一次交互库时间是 $\mathcal O(1)$ 的。