这是一个交互问题!
算术级数或算术数列是一个整数序列,其中元素与其前一个元素的减法 ($$$x_i - x_{i - 1}$$$,其中 $$$i \ge 2$$$) 是常数 - 这种差异称为序列的公差。
也就是说,算术级数是 $$$x_i = x_1 + (i - 1) d$$$ 形式的序列,其中 $$$d$$$ 是该序列的公差。
有一个 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ 的秘密列表。
保证所有元素 $$$a_1, a_2, \ldots, a_n$$$ 都在 $$$0$$$ 和 $$$10^9$$$ 之间(含)。
这个列表很特殊:如果按升序排序,它将形成一个具有正公差的算术级数($$$d > 0$$$)。例如,列表 $$$[14, 24, 9, 19]$$$ 满足此要求,排序后会生成列表 $$$[9, 14, 19, 24]$$$,可以将其生成为 $$$x_n = 9 + 5 \cdot (n - 1)$$$。
此外,您还获得了一个设备,该设备的电池电量已完全耗尽,因此您最多只能使用它执行以下两种类型的 $$$60$$$ 查询:
- 给定值 $$$i$$$ ($$$1 \le i \le n$$$),设备将显示 $$$a_i$$$ 的值。
- 给定值 $$$x$$$ ($$$0 \le x \le 10^9$$$),如果存在值严格大于 $$$x$$$ 的元素,则设备将返回 $$$1$$$,否则将返回 $$$0$$$。
您最多可以使用此特殊设备进行 $$$60$$$ 查询。你能找出序列的最小元素和公差吗?也就是说,等差数列定义中的值 $$$x_1$$$ 和 $$$d$$$ 。请注意,数组 $$$a$$$ 未排序。
互动
交互从单个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) 开始,即整数列表的大小。
然后你可以进行两种类型的查询:
- "? i" ($$$1 \le i \le n$$$) — 获取 $$$a_i$$$ 的值。
- "> x" ($$$0 \le x \le 10^9$$$) — 检查是否存在大于 $$$x$$$ 的元素
查询后以整数形式读取结果 $$$r$$$。
- 对于第一个查询类型,$$$r$$$ 满足 $$$0 \le r \le 10^9$$$。
- 对于第二种查询类型,$$$r$$$ 是 $$$0$$$ 或 $$$1$$$。
- 如果您进行超过 $$$60$$$ 查询或违反查询中的数字范围,您将得到 $$$r = -1$$$。
- 如果您在收到 -1 后终止,您将得到“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
当找出最小元素 $$$x_1$$$ 和公差 $$$d$$$ 时,打印
- “!$$$x_1$$$ $$$d$$$”
之后就退出了。此查询不计入 $$$60$$$ 查询限制。
打印任何查询后,不要忘记输出行尾并刷新输出。否则您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
对于 hack,请使用以下格式:
第一行应包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) — 列表的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 列表的元素。
此外,排序后列表必须形成具有正公差的算术级数。
示例
输入 #1
4 0 1 14 24 9 19
输出 #1
> 25 > 15 ? 1 ? 2 ? 3 ? 4 ! 9 5
注意
请注意,示例交互包含额外的空行,以便更容易阅读。真正的交互不包含任何空行,您也不应该打印任何额外的空行。
示例测试中的列表为 $$$[14, 24, 9, 19]$$$。