#P17762. lis

lis

题目描述

我们称一个数列 aa 是一个长度为 nn 的排列当且仅当 aa 出现了所有不超过 nn 的正整数恰好一次。

对于两个长度为 nn 的排列 a,ba,b,称 aa 的字典序比 bb 小当且仅当存在 1≤i≤n1\le i\le n 使得 a1=b1,a2=b2,⋯ ,ai−1=bi−1a_1=b_1,a_2=b_2,\cdots,a_{i-1}=b_{i-1} 且 ai<bia_i<b_i。

对于一个长度为 nn 的排列 aa,我们定义它的权值为其最长上升子序列的长度。

现在,给定一个长度为 nn 的排列 aa。在一次操作中,你可以选择一个不超过 n−1n-1 的正整数 ii 使得 ai>ai+1a_i>a_{i+1} 并交换 aia_i 与 ai+1a_{i+1}。

你可以进行任意多次操作(也可能不进行操作),请求出在所有可能得到且权值与初始时的 a\boldsymbol{a} 的权值相等的排列中,字典序最小的排列 pp。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0c=0。

对于每组测试数据:

  • 第一行一个正整数 nn,表示排列 aa 的长度;
  • 第二行 nn 个正整数 a1,a2,⋯ ,an(1≤ai≤n)a_1,a_2,\cdots,a_n(1\le a_i\le n),表示给定的排列 aa。

输出格式

对于每组测试数据输出一行 nn 个正整数,表示你求出的排列 pp。

样例

样例 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

该组样例共有 44 组测试数据。

对于第一组测试数据,初始时 a=(2,3,1)a=(2,3,1),权值为 22,可以通过对 i=2i=2 进行一次操作得到 a=(2,1,3)a=(2,1,3),此时排列权值仍为 22,可以证明不能通过操作得到字典序更小的权值为 22 的排列。

对于第三组和第四组测试数据,无法通过操作得到权值不变且字典序比初始的 aa 小的排列 aa,故答案排列即为输入的 aa。

数据范围与提示

对于所有测试数据:

  • T≤20T\le20;
  • 1≤n≤2×105,1≤ai≤n1 \le n \le 2\times10^5,1\le a_i\le n;
  • 保证输入的 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 构成了一个长度为 nn 的排列。
测试点编号 n≤n\le 特殊性质
1∼31\sim 3 88 无
4∼64\sim 6 2020
7∼87\sim 8 100100
9∼119\sim 11 20002000
1212 10510^5 A
13∼1413\sim 14 B
15∼1615\sim 16 C
17∼1917\sim 19 D
20∼2220\sim 22 E
23∼2523\sim 25 2×1052\times 10^5 无
  • 特殊性质 A:对于任意 1≤i≤n1\le i\le n,都有 ai=n−i+1a_i=n-i+1;
  • 特殊性质 B:给定排列的最长上升子序列长度不超过 22;
  • 特殊性质 C:给定排列的最长上升子序列长度不超过 1010;
  • 特殊性质 D:给定排列的最长下降子序列长度不超过 55;
  • 特殊性质 E:保证排列 aa 在 n!n! 种长度为 nn 的排列中随机选取。