AT_awtf2025_a LIS Keeping Swaps

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. 1. $ |S| \lt |T| $ and $ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}) $ . 2. 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 $ .

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 $

For each test case, output the answer.

### Sample Explanation 1 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) $ . ### 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.