CF2205A Simons and Making It Beautiful

Those cling-on troubles that ride my stride — cough up the fee, or step aside. — SHUN, [TAKE IT AWAY](https://open.spotify.com/track/4hpmSSMqgesMBCc3GNopCF) For a permutation $ ^{\text{∗}} $ $ r $ of length $ m $ , we call an index $ i $ ( $ 1\le i\le m $ ) ugly if and only if $ i=\max(\{r_1,r_2,\ldots,r_i\}) $ . Simons has a permutation $ p $ of length $ n $ , and he can perform the following operation on $ p $ at most once: - Choose two indices $ i $ and $ j $ ( $ 1\le i\ne j\le n $ ), then swap $ p_i $ and $ p_j $ . Find a permutation $ q $ that can be obtained from $ p $ by performing the above operation at most once, such that the number of ugly indices in $ q $ is minimized. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line contains an integer $ n $ ( $ 1\le n\le 500 $ ) — the length of $ p $ . The second line contains $ n $ integers $ p_1,p_2,\ldots,p_n $ ( $ 1\le p_i\le n $ , all $ p_i $ -s are distinct) — the elements of $ p $ .

For each test case, print $ n $ integers $ q_1,q_2,\ldots,q_n $ — the permutation you found. If there are multiple possible permutations, you may output any.

In the first test case, Simons can obtain only two possible permutations: $ [1,2] $ and $ [2,1] $ . - For permutation $ [1,2] $ , we can see $ 1=\max(\{1\}) $ and $ 2=\max(\{1,2\}) $ . So there are two ugly indices. - For permutation $ [2,1] $ , we can see $ 1\ne\max(\{2\}) $ and $ 2=\max(\{2,1\}) $ . So there is only one ugly index. Thus, permutation $ [2,1] $ has the minimum count of ugly indices. In the second test case, Simons can obtain permutation $ [2,4,1,3] $ by choosing indices $ 2 $ and $ 4 $ to swap. There is only one ugly index in the permutation: - $ 1\ne \max(\{2\}) $ , so index $ 1 $ is not ugly; - $ 2\ne \max(\{2,4\}) $ , so index $ 2 $ is not ugly; - $ 3\ne \max(\{2,4,1\}) $ , so index $ 3 $ is not ugly; - $ 4=\max(\{2,4,1,3\}) $ , so index $ 4 $ is ugly. In the third test case, note that Simons does not perform the operation.