A12648 | Permutation recovery

Vasya has written some permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ , so for all $1 \leq i \leq n$ it is true that $1 \leq p_i \leq n$ and all $p_1, p_2, \ldots, p_n$ are different. After that he wrote $n$ numbers $next_1, next_2, \ldots, next_n$ . The number $next_i$ is equal to the minimal index $i < j \leq n$ , such that $p_j > p_i$ . If there is no such $j$ let's let's define as $next_i = n + 1$ .

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values $next_i$ are completely lost! If for some $i$ the value $next_i$ is lost, let's say that $next_i = -1$ .

You are given numbers $next_1, next_2, \ldots, next_n$ (maybe some of them are equal to $-1$ ). Help Vasya to find such permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ , that he can write it to the notebook and all numbers $next_i$ , which are not equal to $-1$ , will be correct.

The first line contains one integer $t$ — the number of test cases ( $1 \leq t \leq 100\,000$ ).

Next $2 \cdot t$ lines contains the description of test cases,two lines for each. The first line contains one integer $n$ — the length of the permutation, written by Vasya ( $1 \leq n \leq 500\,000$ ). The second line contains $n$ integers $next_1, next_2, \ldots, next_n$ , separated by spaces ( $next_i = -1$ or $i < next_i \leq n + 1$ ).

It is guaranteed, that the sum of $n$ in all test cases doesn't exceed $500\,000$ .

In hacks you can only use one test case, so $T = 1$ .

Print $T$ lines, in $i$ -th of them answer to the $i$ -th test case.

If there is no such permutations $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ , that Vasya could write, print the only number $-1$ .

In the other case print $n$ different integers $p_1, p_2, \ldots, p_n$ , separated by spaces ( $1 \leq p_i \leq n$ ). All defined values of $next_i$ which are not equal to $-1$ should be computed correctly $p_1, p_2, \ldots, p_n$ using defenition given in the statement of the problem. If there exists more than one solution you can find any of them.