[Solution] Permutation Restoration solution codeforces

Permutation Restoration solution codeforces – Monocarp had a permutation 𝑎a of 𝑛n integers 1122, …, 𝑛n (a permutation is an array where each element from 11 to 𝑛n occurs exactly once).

Table of Contents

[Solution] Permutation Restoration solution codeforces

Then Monocarp calculated an array of integers 𝑏b of size 𝑛n, where 𝑏𝑖=𝑖𝑎𝑖bi=⌊iai⌋. For example, if the permutation 𝑎a is [2,1,4,3][2,1,4,3], then the array 𝑏b is equal to [12,21,34,43]=[0,2,0,1][⌊12⌋,⌊21⌋,⌊34⌋,⌊43⌋]=[0,2,0,1].

Unfortunately, the Monocarp has lost his permutation, so he wants to restore it. Your task is to find a permutation 𝑎a that corresponds to the given array 𝑏b. If there are multiple possible permutations, then print any of them. The tests are constructed in such a way that least one suitable permutation exists.

Input

The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — number of test cases.

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

The second line contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (0𝑏𝑖𝑛0≤bi≤n).

Additional constrains on the input:

  • the sum of 𝑛n over test cases does not exceed 51055⋅105;
  • there exists at least one permutation 𝑎a that would yield this array 𝑏b.

[Solution] Permutation Restoration solution codeforces

For each test case, print 𝑛n integers — a permutation 𝑎a that corresponds to the given array 𝑏b. If there are multiple possible permutations, then print any of them.

Example
input

Copy
4
4
0 2 0 1
2
1 1
5
0 0 1 4 1
3
0 1 3
output

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

 

For Solution

Click Here

Leave a Comment