Elemental Decompress solution codeforces

Elemental Decompress solution codeforces – You are given an array 𝑎a of 𝑛n integers.

Find two permutations 𝑝p and 𝑞q of length 𝑛n such that max(𝑝𝑖,𝑞𝑖)=𝑎𝑖max(pi,qi)=ai for all 1𝑖𝑛1≤i≤n or report that such 𝑝p and 𝑞q do not exist.

Elemental Decompress solution codeforces

 A permutation of length 𝑛n is an array consisting of 𝑛n distinct integers from 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).

Input

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

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

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

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

Elemental Decompress solution codeforces

For each test case, if there do not exist 𝑝p and 𝑞q that satisfy the conditions, output “NO” (without quotes).

Otherwise, output “YES” (without quotes) and then output 22 lines. The first line should contain 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn and the second line should contain 𝑛n integers 𝑞1,𝑞2,,𝑞𝑛q1,q2,…,qn.

Also read: Quick Sort solution codeforces

If there are multiple solutions, you may output any of them.

You can output “YES” and “NO” in any case (for example, strings “yEs“, “yes” and “Yes” will be recognized as a positive response).

Elemental Decompress solution codeforces

input

Copy
3
1
1
5
5 3 4 2 5
2
1 1

output

Copy
YES
1 
1 
YES
1 3 4 2 5 
5 2 3 1 4 
NO

Elemental Decompress solution codeforces

In the first test case, 𝑝=𝑞=[1]p=q=[1]. It is correct since 𝑎1=𝑚𝑎𝑥(𝑝1,𝑞1)=1a1=max(p1,q1)=1.

In the second test case, 𝑝=[1,3,4,2,5]p=[1,3,4,2,5] and 𝑞=[5,2,3,1,4]q=[5,2,3,1,4]. It is correct since:

  • 𝑎1=max(𝑝1,𝑞1)=max(1,5)=5a1=max(p1,q1)=max(1,5)=5,
  • 𝑎2=max(𝑝2,𝑞2)=max(3,2)=3a2=max(p2,q2)=max(3,2)=3,
  • 𝑎3=max(𝑝3,𝑞3)=max(4,3)=4a3=max(p3,q3)=max(4,3)=4,
  • 𝑎4=max(𝑝4,𝑞4)=max(2,1)=2a4=max(p4,q4)=max(2,1)=2,
  • 𝑎5=max(𝑝5,𝑞5)=max(5,4)=5a5=max(p5,q5)=max(5,4)=5.

In the third test case, one can show that no such 𝑝p and 𝑞q exist.

Leave a Reply

Your email address will not be published. Required fields are marked *