题目描述

本题为交互题。

鲤鱼在一次海底探险中，发现了一处由 $n$ 个古老装置组成的遗迹。这些装置从左到右编号为 $1,2,\dots,n$。鲤鱼得知其中恰好有两个装置仍然保存着能量。

由于这种能量没有具体形态，无法直接观测，因此必须使用专门的探测器进行扫描。

每一次，鲤鱼都可以选择一段连续的装置编号区间 $[l,r]$ 进行扫描，探测器会告诉他：在这段区间中，一共有多少个拥有能量的装置。由于整个遗迹中只有两个有效装置，因此一次扫描的结果只可能是 $0$、$1$ 或 $2$。

然而，探测器的电量已经所剩无几，最多只能再使用 $50$ 次。

请你帮助鲤鱼，在不超过 $50$ 次扫描的情况下，确定两个有效装置的位置

输入格式

第一行输入一个正整数 $n$，表示装置的数量。

输出格式

本题为交互题，具体输出方式见「交互格式」。

温馨提示：

• 输出答案时，应当从小到大输出（即先输出较小的位置，再输出较大的位置）；
• 与交互器交互时，不应输出多余的空格，否则可能会得到 Wrong Answer 的结果。

10

1

1

0

1

1

? 2 6

? 7 10

? 1 3

? 4 7

? 8 9

! 4 9

说明/提示

数据范围

对于所有测试数据，满足 $2\le n\le 2\times10^5$。

隐藏的两个位置满足 $1\le x<y\le n$。

询问次数限制

对于每组测试数据，你最多可以进行 $50$ 次形如：? l r 的询问。

如果询问次数超过 $50$ 次，则会被判定为答案错误。

交互格式

每次输出询问后，都必须立即刷新输出缓冲区，否则程序可能会一直等待交互器返回结果。

C++

可以使用：

cout << "? " << l << " " << r << endl;

其中 endl 会自动刷新输出缓冲区。

也可以使用：

cout << "? " << l << " " << r << '\n';
cout.flush();

当确定答案后，也应输出最终答案并刷新，例如：

cout << "! " << x << " " << y << endl;

C

可以使用：

printf("? %d %d\n", l, r);
fflush(stdout);

其中 fflush(stdout) 用于刷新标准输出缓冲区。

当确定答案后，也应输出最终答案并刷新，例如：

printf("! %d %d\n", x, y);
fflush(stdout);

Python

可以使用：

print("?", l, r, flush=True)

其中 flush=True 会立即刷新输出缓冲区。

也可以使用：

import sys

print("?", l, r)
sys.stdout.flush()

当确定答案后，也应输出最终答案并刷新，例如：

print("!", x, y, flush=True)

样例解释

假设两个有效装置的位置分别为 $4$ 和 $9$。

对于询问：

? 2 6

区间 $[2,6]$ 中恰好包含一个有效装置，因此交互器返回 $1$。

对于询问：

? 7 10

区间 $[7,10]$ 中也恰好包含一个有效装置，因此交互器返回 $1$。

对于询问：

? 1 3

区间 $[1,3]$ 中不存在有效装置，因此交互器返回 $0$。

对于询问：

? 4 7

区间 $[4,7]$ 中恰好包含一个有效装置，因此交互器返回 $1$。

对于询问：

? 8 9

区间 $[8,9]$ 中恰好包含一个有效装置，因此交互器返回 $1$。

最终程序确定两个有效装置的位置分别为 $4$ 和 $9$，因此输出：

! 4 9

注意：该样例仅用于说明交互格式，并不代表一种正确的询问策略。

在不同实际测试中，有效装置的位置不同。