{"problem":{"name":"LIS Keeping Swaps","description":{"content":"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 valu","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"awtf2025_a"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"awtf2025_a","tags":[],"sample_group":[["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","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)$."]],"created_at":"2026-03-03 11:01:13"}}