[Solution] Array Shuffling solution codeforces

Array Shuffling solution codeforces – oolimry has an array 𝑎a of length 𝑛n which he really likes. Today, you have changed his array to 𝑏b, a permutation of 𝑎a, to make him sad.

[Solution] Array Shuffling solution codeforces

Because oolimry is only a duck, he can only perform the following operation to restore his array:

  • Choose two integers 𝑖,𝑗i,j such that 1𝑖,𝑗𝑛1≤i,j≤n.
  • Swap 𝑏𝑖bi and 𝑏𝑗bj.

The sadness of the array 𝑏b is the minimum number of operations needed to transform 𝑏b into 𝑎a.

Given the array 𝑎a, find any array 𝑏b which is a permutation of 𝑎a that has the maximum sadness over all permutations of the array 𝑎a.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105)  — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤n)  — elements of the array 𝑎a.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Array Shuffling solution codeforces

For each test case, print 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn — describing the array 𝑏b. If there are multiple answers, you may print any.

Example
input

Copy
2
2
2 1
4
1 2 3 3
output

Copy
1 2
3 3 2 1

Array Shuffling solution codeforces

In the first test case, the array [1,2][1,2] has sadness 11. We can transform [1,2][1,2] into [2,1][2,1] using one operation with (𝑖,𝑗)=(1,2)(i,j)=(1,2).

In the second test case, the array [3,3,2,1][3,3,2,1] has sadness 22. We can transform [3,3,2,1][3,3,2,1] into [1,2,3,3][1,2,3,3] with two operations with (𝑖,𝑗)=(1,4)(i,j)=(1,4) and (𝑖,𝑗)=(2,3)(i,j)=(2,3) respectively.

 

For Solution

Click here

Leave a Comment