题目描述
我们称一个数列 a 是一个长度为 n 的排列当且仅当 a 出现了所有不超过 n 的正整数恰好一次。
对于两个长度为 n 的排列 a,b,称 a 的字典序比 b 小当且仅当存在 1≤i≤n 使得 a1=b1,a2=b2,⋯,ai−1=bi−1 且 ai<bi。
对于一个长度为 n 的排列 a,我们定义它的权值为其最长上升子序列的长度。
现在,给定一个长度为 n 的排列 a。在一次操作中,你可以选择一个不超过 n−1 的正整数 i 使得 ai>ai+1 并交换 ai 与 ai+1。
你可以进行任意多次操作(也可能不进行操作),请求出在所有可能得到且权值与初始时的 a 的权值相等的排列中,字典序最小的排列 p。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0。
对于每组测试数据:
- 第一行一个正整数 n,表示排列 a 的长度;
- 第二行 n 个正整数 a1,a2,⋯,an(1≤ai≤n),表示给定的排列 a。
输出格式
对于每组测试数据输出一行 n 个正整数,表示你求出的排列 p。
样例
样例 1
0 4
3
2 3 1
7
5 7 6 4 2 3 1
8
4 3 2 1 5 6 7 8
9
3 2 1 6 5 4 9 8 7
2 1 3
5 2 1 7 6 4 3
4 3 2 1 5 6 7 8
3 2 1 6 5 4 9 8 7
样例解释 1
该组样例共有 4 组测试数据。
对于第一组测试数据,初始时 a=(2,3,1),权值为 2,可以通过对 i=2 进行一次操作得到 a=(2,1,3),此时排列权值仍为 2,可以证明不能通过操作得到字典序更小的权值为 2 的排列。
对于第三组和第四组测试数据,无法通过操作得到权值不变且字典序比初始的 a 小的排列 a,故答案排列即为输入的 a。
数据范围与提示
对于所有测试数据:
- T≤20;
- 1≤n≤2×105,1≤ai≤n;
- 保证输入的 a1,a2,⋯,an 构成了一个长度为 n 的排列。
| 测试点编号 |
n≤ |
特殊性质 |
| 1∼3 |
8 |
无 |
| 4∼6 |
20 |
| 7∼8 |
100 |
| 9∼11 |
2000 |
| 12 |
105 |
A |
| 13∼14 |
B |
| 15∼16 |
C |
| 17∼19 |
D |
| 20∼22 |
E |
| 23∼25 |
2×105 |
无 |
- 特殊性质 A:对于任意 1≤i≤n,都有 ai=n−i+1;
- 特殊性质 B:给定排列的最长上升子序列长度不超过 2;
- 特殊性质 C:给定排列的最长上升子序列长度不超过 10;
- 特殊性质 D:给定排列的最长下降子序列长度不超过 5;
- 特殊性质 E:保证排列 a 在 n! 种长度为 n 的排列中随机选取。