{"raw_statement":[{"iden":"problem statement","content":"You are given a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$.\nYou can perform the following operation zero or more times:\n\n*   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:\n    *   $P_i>P_{i+1}$ holds immediately before the operation.\n    *   The operation does not change the length of the longest increasing subsequence of $P$.\n\nFind the lexicographically smallest permutation among all permutations that can be obtained as $P$ after operations.\nSolve $T$ test cases for each input.\nWhat 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.\n\n1.  $|S| \\lt |T|$ and $(S_1,S_2,\\ldots,S_{|S|}) = (T_1,T_2,\\ldots,T_{|S|})$.\n2.  There exists an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ such that both of the following hold:\n    *   $(S_1,S_2,\\ldots,S_{i-1}) = (T_1,T_2,\\ldots,T_{i-1})$.\n    *   $S_i$ is (numerically) smaller than $T_i$."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 250000$\n*   $1 \\leq N \\leq 250000$\n*   $P$ is a permutation of $(1,2,\\ldots,N)$.\n*   The sum of $N$ over all test cases in each input does not exceed $250000$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$P_1$ $P_2$ $\\cdots$ $P_N$"},{"iden":"sample input 1","content":"4\n3\n2 3 1\n3\n3 2 1\n7\n5 7 6 4 2 3 1\n15\n6 4 5 14 15 1 3 9 12 8 10 2 7 13 11"},{"iden":"sample output 1","content":"2 1 3\n3 2 1\n5 2 1 7 6 4 3\n4 1 6 5 3 2 9 8 7 14 12 10 15 13 11\n\nLet 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)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}