CF1158C.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 \lt j \leq n$, such that $p_j \gt 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.

瓦西娅写下了某个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$，即对所有 $1 \leq i \leq n$ 均满足 $1 \leq p_i \leq n$，且 $p_1, p_2, \ldots, p_n$ 互不相同。随后，他写下了 $n$ 个数 $next_1, next_2, \ldots, next_n$。其中，$next_i$ 等于满足 $i \lt j \leq n$ 且 $p_j \gt p_i$ 的最小下标 $j$；若不存在这样的 $j$，则定义 $next_i = n + 1$。

当晚瓦西娅放学回家时因下雨导致笔记本被淋湿，部分数字现已无法辨认。排列本身及部分 $next_i$ 的值已完全丢失！若对某个 $i$，其 $next_i$ 的值丢失，则记为 $next_i = -1$。

现给出 $next_1, next_2, \ldots, next_n$（其中部分值可能为 $-1$）。请帮助瓦西娅找出一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$，使得将其写入笔记本后，所有不等于 $-1$ 的 $next_i$ 值均正确。

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 \lt 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$.

第一行包含一个整数 $t$ —— 测试用例的数量（$1 \leq t \leq 100\,000$）。

接下来的 $2 \cdot t$ 行描述了测试用例，每个测试用例占两行。第一行包含一个整数 $n$ —— Vasya 写下的排列的长度（$1 \leq n \leq 500\,000$）。第二行包含 $n$ 个整数 $next_1, next_2, \ldots, next_n$，以空格分隔（其中 $next_i = -1$ 或 $i \lt next_i \leq n + 1$）。

保证所有测试用例中 $n$ 的总和不超过 $500\,000$。

在 hack 中，你只能使用一个测试用例，因此 $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.

输出 $T$ 行，其中第 $i$ 行为第 $i$ 个测试用例的答案。

如果不存在满足条件的、由 $1$ 到 $n$ 的整数组成的排列 $p_1, p_2, \ldots, p_n$（即 Vasya 可能写出的排列），则仅输出数字 $-1$。

否则，输出 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$，以空格分隔（需满足 $1 \leq p_i \leq n$）。所有不等于 $-1$ 的 $next_i$ 值，均须根据题目陈述中所给定义，利用该排列 $p_1, p_2, \ldots, p_n$ 正确计算得出。若存在多个可行解，输出任意一个即可。

In the first test case for permutation $p = [1, 2, 3]$ Vasya should write $next = [2, 3, 4]$, because each number in permutation is less than next. It's easy to see, that it is the only satisfying permutation.

In the third test case, any permutation can be the answer because all numbers $next_i$ are lost.

In the fourth test case, there is no satisfying permutation, so the answer is $-1$.

在第一个测试用例中，对于排列 $p = [1, 2, 3]$，Vasya 应写出 $next = [2, 3, 4]$，因为排列中的每个数均小于其对应的 $next$ 中的数。显然，这是唯一满足条件的排列。

在第三个测试用例中，任意排列均可作为答案，因为所有 $next_i$ 均已丢失。

在第四个测试用例中，不存在满足条件的排列，因此答案为 $-1$。