雷丢失了他的阵列,需要通过询问奥姆卡来找到它。 Omkar愿意透露,该阵列具有以下品质:
1. 数组有 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 个元素。
2. 数组 $$$a_i$$$ 中的每个元素都是 $$$1 \le a_i \le 10^9.$$$ 范围内的整数
3. 数组按非降序排序。
Ray 被允许向 Omkar 发送一系列查询。查询由两个整数 $$$l$$$ 和 $$$r$$$ 组成,使得 $$$1 \le l \le r \le n$$$。 Omkar 将返回两个整数 $$$x$$$ 和 $$$f$$$。 $$$x$$$ 是从索引 $$$l$$$ 到索引 $$$r$$$ 的子数组的众数。数组的众数由出现最频繁的数字定义。如果有多个出现次数最多的数字,则将其中最小的数字视为众数。 $$$f$$$ 是$$$x$$$ 在查询的子数组中出现的次数。
该数组具有 $$$k$$$ ($$$1 \le k \le \min(25000,n)$$$) 个不同元素。然而,由于雷的罪孽,奥姆卡不会告诉雷$$$k$$$是什么。 Ray 最多可以发送 $$$4k$$$ 查询。
帮助雷找到他丢失的阵列。
输入
输入的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$),它等于您要查找的数组的长度。
互动
交互从读取 $$$n$$$ 开始。
然后你可以进行一种类型的查询:
- "$$$? \enspace l \enspace r$$$" ($$$1 \le l \le r \le n$$$) 其中 $$$l$$$ 和 $$$r$$$ 是您要查询的子数组的边界。
每个查询的答案将采用“$$$x \enspace f$$$”的形式,其中 $$$x$$$ 是子数组的众数,$$$f$$$ 是 $$$x$$$ 在子数组中出现的次数。
- $$$x$$$ 满足 ($$$1 \leq x \leq 10^9$$$)。
- $$$f$$$ 满足 ($$$1 \leq f \leq r-l+1$$$)。
- 如果您进行超过 $$$4k$$$ 查询或违反查询中的数字范围,您将得到输出“-1”。
- 如果您在收到响应“$$$-1$$$”后终止,您将得到“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
要输出您的答案,请打印:
- "$$$! \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_{n-1} \enspace a_n$$$" 这是一个感叹号,后跟数组,每个元素之间有一个空格。
之后就退出了。此查询不计入 $$$4k$$$ 查询限制。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
要破解,请在第一行输出 $$$1$$$ 整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。在第二行输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_{n-1}, a_n$$$ 以空格分隔,这样最多有 $$$25000$$$ 不同的数字,并且 $$$a_j \le a_{j+1}$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$j$$$。
示例
输入 #1
6 2 2 2 2 3 2 2 1
输出 #1
? 1 6 ? 1 3 ? 4 6 ? 3 4 ! 1 2 2 3 3 4
注意
第一个查询是 $$$l=1$$$ 和 $$$r=6$$$。众数为 $$$2$$$,$$$2$$$ 出现 $$$2$$$ 次,因此 $$$x=2$$$ 且 $$$f=2$$$。请注意,$$$3$$$ 也出现了两次,但输出了$$$2$$$,因为$$$2$$$ 较小。
第二个查询是 $$$l=1$$$ 和 $$$r=3$$$。众数为 $$$2$$$ 且 $$$2$$$ 在索引为 $$$[1,3]$$$ 的子数组中出现两次。
第三个查询是 $$$l=4$$$ 和 $$$r=6$$$。众数为 $$$3$$$ 且 $$$3$$$ 在索引为 $$$[4,6]$$$ 的子数组中出现两次。
第四个查询是$$$l=3$$$ 和$$$r=4$$$。众数为 $$$2$$$,在索引为 $$$[3,4]$$$ 的子数组中出现一次。请注意,$$$3$$$ 在该范围内也出现一次,但 $$$2$$$ 小于 $$$3$$$。