/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます．
あなたは以下の操作を 0 回以上行うことができます．
- 整数 i (1 \leq i \leq N-1) を選び，P_i と P_{i+1} の値を入れ替える．
ただしここで，以下の条件を両方満たす必要がある．
- 操作の直前において，P_i>P_{i+1} が成立する．
- 操作の前後で，P の最長増加部分列の長さが変化しない．
操作後の P としてありうる順列のうち，辞書順で最小のものを求めてください．
1 つの入力につき，T 個のテストケースを解いてください．
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 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 が存在して，下記の 2 つがともに成り立つ．
- (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) の順列である
- 1 つの入力における 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
1 つめのテストケースについて説明します． P=(2,3,1) に対しては，i=1 では操作できませんが，i=2 を選んで操作することが可能です． 操作後 P=(2,1,3) となりますが，ここから更に操作することはできません． P=(2,3,1) からスタートして到達できる順列の中で辞書順最小のものは (2,1,3) になります．
Score : 800 points
Problem Statement
You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
You can perform the following operation zero or more times:
- Choose an integer i (1 \leq i \leq N-1) and swap the values of P_i and P_{i+1}.
Here, both of the following conditions must be satisfied:
- P_i>P_{i+1} holds immediately before the operation.
- The operation does not change the length of the longest increasing subsequence of P.
Find the lexicographically smallest permutation among all permutations that can be obtained as P after operations.
Solve T test cases for each input.
What is lexicographic order on sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if either of the following conditions 1. and 2. holds. Here, |S| and |T| represent the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is (numerically) smaller than T_i.
Constraints
- 1 \leq T \leq 250000
- 1 \leq N \leq 250000
- P is a permutation of (1,2,\ldots,N).
- The sum of N over all test cases in each input does not exceed 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each test case is given in the following format:
N P_1 P_2 \cdots P_N
Output
For each test case, output the answer.
Sample Input 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
Sample Output 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
Let us explain the first test case. For P=(2,3,1), the operation cannot be performed with i=1, but can be performed with i=2. After the operation, P=(2,1,3), and no further operations can be performed from here. Among the permutations reachable starting from P=(2,3,1), the lexicographically smallest one is (2,1,3).