AT_awtf2025_a LIS Keeping Swaps

$ (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 $ の長さを表します． 1. $ |S| \lt |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}) $ ． 2. ある整数 $ 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 $ より（数として）小さい．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $

各テストケースに対し，答えを出力せよ．

### Sample Explanation 1 $ 1 $ つめのテストケースについて説明します． $ P=(2,3,1) $ に対しては， $ i=1 $ では操作できませんが， $ i=2 $ を選んで操作することが可能です． 操作後 $ P=(2,1,3) $ となりますが，ここから更に操作することはできません． $ P=(2,3,1) $ からスタートして到達できる順列の中で辞書順最小のものは $ (2,1,3) $ になります． ### Constraints - $ 1 \leq T \leq 250000 $ - $ 1 \leq N \leq 250000 $ - $ P $ は $ (1,2,\ldots,N) $ の順列である - $ 1 $ つの入力における $ N $ の総和は $ 250000 $ を超えない - 入力はすべて整数