分数: 800 点
问题陈述
给你一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
您可以执行以下操作零次或多次:
- 选择一个整数 i (1 \leq i \leq N-1)并交换值 P_i 和 P_{i+1}。
这里,必须满足以下两个条件:
- P_i>P_{i+1} 在操作之前立即保持。
- 该操作不会改变最长递增子序列的长度 P.
找到所有排列中按字典顺序排列的最小排列,可以通过以下方式获得 P 操作后。
解决 T 每个输入的测试用例。
序列的字典顺序是什么?
一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果以下条件 1. 和 2. 之一成立。 在这里, |S| 和 |T| 代表的长度 S 和 T。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i (在数值上)小于 T_i.
约束
- 1 \leq T \leq 250000
- 1 \leq N \leq 250000
- P 是一个排列 (1,2,\ldots,N).
- 总和 N 每个输入中的所有测试用例不超过 250000.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例均按以下格式给出:
N P_1 P_2 \cdots P_N
输出
对于每个测试用例,输出答案。
示例输入 1
4 3 2 3 1 3 3 2 1 7 5 7 6 4 2 3 1 15 6 4 5 14 15 1 3 9 12 8 10 2 7 13 11
示例输出 1
2 1 3 3 2 1 5 2 1 7 6 4 3 4 1 6 5 3 2 9 8 7 14 12 10 15 13 11
让我们解释一下第一个测试用例。 对于 P=(2,3,1),无法执行该操作 i=1,但可以执行 i=2。 手术后, P=(2,1,3),并且无法从这里执行进一步的操作。 在可到达的排列中,从 P=(2,3,1),字典顺序最小的一个是 (2,1,3).