[DTCPC 2024] The last permutation

**本题题目背景不均为虚构，不影射任何人**。 小 L 是小 L 初中时的白月光。 有一天，小 L 在朋友圈说要玩农，小 L 火速研究怎么下载王者。 第二天，小 L 在朋友圈说要玩吃鸡，小 L 火速研究怎么下载 pubg。 但小 L 很快就和小 L 分手了，小 L 最后的情思化作一个排列。遗憾的是，小 L 并不情愿告诉大家。 不过在你的不断追问下，小 L 还是同意回答几个关于排列的问题。

现存在一个长度为 $n$ 的隐藏排列 $p$。你可以进行如下询问若干次：选择三元组 $(l,r,k)$，满足 $1\leq l\leq r\leq n$，$1\leq k\leq r - l + 1$，交互库会返回下标在 $[l,r]$ 内的第 $k$ 大值。 对于一次询问操作，其代价为 $\frac{1}{r-l+1}$，你需要在不超过 $11.8$ 的代价内得出排列。 交互库不自适应，也就是说，你所需得到的排列在交互开始前就已经确定。

输入第一行是一个正整数 $t$ ($1 \le t \le 5$) 表示测试组数。 对于每组数据，输入一行 $n$ ($1 \le n \le 1000$) 表示排列 $p$ 的长度。 当你已经得到排列，你应当输出形如 `! p1 p2 ... pn` 表示你得出的排列。 本题使用 IO 交互模式。 ### 交互格式 - `? l r k`，询问下标在 $[l,r]$ 内的第 $k$ 大值。 - `! p1 p2 p3 ... pn`，输出答案。 请注意：在每组数据中，请保证询问操作的代价总和不超过 $11.8$。 需要注意的是，在每一次操作后，需要调用以下函数刷新缓存： - 对于 C/C++：`fflush(stdout);` - 对于 C++：`std::cout << std::flush;` - 对于 Java：`System.out.flush();` - 对于 Python：`stdout.flush();` - 对于 Pascal：`flush(output);` 对于其他语言，请自行查阅对应语言的帮助文档。

见「交互格式」。

1
5

2

3

1

4

? 1 1 1

? 2 2 1

? 3 3 1

? 4 4 1

! 2 3 1 4 5