这是一个交互问题。
我们向您隐藏了长度为 $$$n$$$ 的排列 $$$p$$$,由从 $$$1$$$ 到 $$$n$$$ 的元素组成。你想猜一下。为此,您可以给我们 2 个不同的索引 $$$i$$$ 和 $$$j$$$,我们将回复 $$$p_{i} \bmod p_{j}$$$ ($$$p_{i}$$$ 除以 $$$p_{j}$$$ 的余数)。
我们有足够的耐心来回答最多 $$$2 \cdot n$$$ 查询,因此您应该符合此限制。你能做到吗?
提醒一下,长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
输入
输入的唯一行包含单个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) — 排列的长度。
互动
交互从读取 $$$n$$$ 开始。
那么你最多可以通过以下方式进行 $$$2 \cdot n$$$ 查询:
- “?x y”($$$1 \le x,y \le n,x \ne y$$$)。
在每一个之后,您应该读取一个整数 $$$k$$$,它等于 $$$p_x \bmod p_y$$$。
当您猜出排列后,打印一行“!”(不带引号),后跟数组 $$$p$$$ 并退出。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
收到“-1”后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客格式
在第一行输出 $$$n$$$ ($$$1 \le n \le 10^4$$$)。在第二行中打印 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ 的排列。
示例
输入 #1
3 1 2 1 0
输出 #1
? 1 2 ? 3 2 ? 1 3 ? 2 1 ! 1 3 2