这是一个交互问题。
在工作拖延时,精灵 Dilhan 偶然发现了两个数组 $$$a$$$ 和 $$$b$$$。最初,它们都由单个整数 $$$2^k$$$ 组成(即 $$$a=b=[2^k]$$$),其中 $$$k$$$ 是非负整数。
Dilhan 然后以任意顺序应用以下两种类型的操作任意次数(可能为零):
- 展平 — 选择 $$$a$$$ 或 $$$b$$$,然后选择 任何 元素 $$$x$$$ 即 最大 在该数组中($$$x$$$ 确实 不 需要在另一个数组中最大)。然后,在同一位置将 $$$x$$$ 替换为 $$$\frac x2$$$ 的两个副本。仅当 $$$x$$$ 为偶数时才能应用此操作。
- 连接 — 设置 两者 $$$a$$$ 和 $$$b$$$ 为 $$$a+b$$$,其中 $$$+$$$ 表示数组串联。
执行这些操作后,Dilhan 会丢弃 $$$b$$$,对你隐藏 $$$a$$$,并向你发起游戏挑战。
令 $$$n$$$ 为隐藏数组 $$$a$$$ 的长度。您可以进行以下查询:
- 选择一个区间 $$$[l, r]$$$ ($$$1\le l\le r\le n$$$),Dilhan 会告诉你总和 $$$a_l+a_{l+1}+\cdots+a_r$$$。
通过进行最多 $$$300$$$ 查询来确定 $$$a$$$ 的最大元素的值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — $$$a$$$ 的长度。
保证$$$1\le a_i\le 2^{30}$$$,并且可以通过语句中描述的过程生成数组$$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
互动
对于每个测试用例,首先给您一个整数 $$$n$$$ — 隐藏数组 $$$a$$$ 的长度。然后您最多可以进行 $$$300$$$ 查询。
要进行查询,请按以下格式打印一行:
- $$$\texttt{?}\;l\;r$$$ ($$$1\le l\le r\le n$$$) — 为查询选择的索引。
打印查询后,交互器将返回一个整数 - 总和 $$$a_l+a_{l+1}+\ldots+a_r$$$。
要报告您已确定 $$$a$$$ 的最大元素的值,请按以下格式打印您的答案:
- $$$\texttt{!}\; m$$$ ($$$1\le m\le 2^{30}$$$) — 最大元素的值。
打印答案不算作 $$$300$$$ 查询之一。
打印答案后,继续下一个测试用例。如果当前测试用例是最后一个,则终止程序。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
这个问题中的交互者是 不 自适应。换句话说,数组 $$$a$$$ 在任何查询之前都是固定的,并且在交互过程中不会改变。
在此问题中,黑客被禁用。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
4 11 9 4 12 1 1 8 4 4 4 4 8
输出复制
? 3 8 ? 1 4 ? 5 11 ! 2 ? 1 1 ! 1 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ! 4 ! 1073741824
注意
在第一个测试用例中,Dilhan 的隐藏数组 $$$a$$$ 是 $$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$。它可以通过以下过程生成:
| # | 类型 | 操作后$$$a$$$ | 操作后$$$b$$$ |
| 0 | $$$[4]$$$ | $$$[4]$$$ | |
| 1 | 压平$$$a$$$ | $$$[\下划线 4] \到 {[2, 2]}$$$ | $$$[4]$$$ |
| 2 | 压平$$$b$$$ | $$$[2, 2]$$$ | $$$[\下划线 4] \到 {[2, 2]}$$$ |
| 3 | 压平$$$a$$$ | $$$[2, \下划线 2] \到 {[2, 1, 1]}$$$ | $$$[2, 2]$$$ |
| 4 | 连接 | $$$[2, 1, 1, 2, 2]$$$ | $$$[2, 1, 1, 2, 2]$$$ |
| 5 | 压平$$$a$$$ | $$$[\下划线 2, 1, 1, 2, 2]\到 {[1, 1, 1, 1, 2, 2]}$$$ | $$$[2, 1, 1, 2, 2]$$$ |
| 6 | 连接 | $$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$ | $$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$ |
- 对于查询$$$\mathtt{?\;3\;8}$$$,陪审团回答$$$1+1+2+2+2+1=9$$$;
- 对于查询$$$\mathtt{?\;1\;4}$$$,陪审团回答$$$1+1+1+1=4$$$;
- 对于查询$$$\mathtt{?\;5\;11}$$$,陪审团的回答是$$$2+2+2+1+1+2+2=12$$$。
$$$a$$$ 的最大元素值为$$$2$$$。
在第二个测试用例中,数组 $$$a$$$ 只有一个元素。通过查询,唯一元素的值为$$$1$$$,而且也一定是最大值。
在第三个测试用例中,Dilhan 的隐藏数组 $$$a$$$ 是 $$$[4, 4, 4, 4, 4, 4, 4, 4]$$$。它可以通过以下过程生成:
| # | 类型 | 操作后$$$a$$$ | 操作后$$$b$$$ |
| 0 | $$$[4]$$$ | $$$[4]$$$ | |
| 1 | 连接 | $$$[4, 4]$$$ | $$$[4, 4]$$$ |
| 2 | 连接 | $$$[4, 4, 4, 4]$$$ | $$$[4, 4, 4, 4]$$$ |
| 3 | 连接 | $$$[4, 4, 4, 4, 4, 4, 4, 4]$$$ | $$$[4, 4, 4, 4, 4, 4, 4, 4]$$$ |
而$$$a$$$的最大元素值为$$$4$$$。
在第四个测试用例中,Dilhan 的隐藏数组 $$$a$$$ 为 $$$[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$$$。