[WFOI - 01] 猜数（guess）

**这是一道交互题。交互库自适应。请注意特殊的时间限制。** **每次输出后请记得清空缓存** 简化题意：[$\texttt{Link}$](https://www.luogu.com.cn/paste/xx7sa8go)。

你需要猜一个正整数 $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}$ | $10^5$ | 对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le q,\forall u\le n$，$\forall v\in\{0,1,2\}$。 保证每询问一次交互库时间是 $\mathcal O(1)$ 的。