[Solution] Permutation Restoration Codeforces Solution

D. Permutation Restoration

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Monocarp had a permutation a$a$ of n$n$ integers 1$1$, 2$2$, ..., n$n$ (a permutation is an array where each element from 1$1$ to n$n$ occurs exactly once).

Then Monocarp calculated an array of integers b$b$ of size n$n$, where bi=⌊iai⌋$b_i=\lfloor \frac{i}{a_i}\rfloor$. For example, if the permutation a$a$ is [2,1,4,3]$[2,1,4,3]$, then the array b$b$ is equal to [⌊12⌋,⌊21⌋,⌊34⌋,⌊43⌋]=[0,2,0,1]$[\lfloor \frac{1}{2}\rfloor ,\lfloor \frac{2}{1}\rfloor ,\lfloor \frac{3}{4}\rfloor ,\lfloor \frac{4}{3}\rfloor ]=[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$a$ that corresponds to the given array b$b$. If there are multiple possible permutations, then print

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 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$t$ (1≤t≤105$1\le t\le {10}^5$) — number of test cases.

The first line of each test case contains a single integer n$n$ (1≤n≤5⋅105$1\le n\le 5\cdot {10}^5$).

Grass Field Codeforces Solution

Permutation Codeforces Solution

Schedule Management Codeforces Solution

Permutation Restoration Codeforces Solution

Text Editor Codeforces Solution

Points Codeforces Solution 

The second line contains n$n$ integers b1,b2,…,bn$b_1,b_2,\dots ,b_n$ (0≤bi≤n$0\le b_i\le n$).

Additional constrains on the input:

• the sum of n$n$ over test cases does not exceed 5⋅105$5\cdot {10}^5$;
• there exists at least one permutation a$a$ that would yield this array b$b$.

Output

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