C. Восстановление перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася написал в тетради некоторую перестановку $$$p_1, p_2, \ldots, p_n$$$ чисел от $$$1$$$ до $$$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 < j \leq n$$$, такому что $$$p_j > p_i$$$. Если такого $$$j$$$ не существует, то определим значение как $$$next_i = n + 1$$$.

Вечером Вася шел домой из школы, и из-за дождя тетрадь намокла. Теперь некоторые написанные числа невозможно разобрать. Перестановка, а также некоторые значения $$$next_i$$$ полностью утеряны! Если для какого-то $$$i$$$ значение $$$next_i$$$ теперь неизвестно, то скажем, что $$$next_i = -1$$$.

Вам даны значения $$$next_1, next_2, \ldots, next_n$$$ (возможно, некоторые числа теперь равны $$$-1$$$). Помогите Васе найти любую такую перестановку $$$p_1, p_2, \ldots, p_n$$$ чисел от $$$1$$$ до $$$n$$$, что он может записать её в тетрадь, и все значения $$$next_i$$$, не равные $$$-1$$$, будут посчитаны правильно.

Входные данные

В первой строке находится одно целое число $$$t$$$ — количество тестовых случаев ($$$1 \leq t \leq 100\,000$$$).

В следующих $$$2 \cdot t$$$ строках находится описание тестовых случаев, по две строки на каждый. В первой из этих строк находится единственное целое число $$$n$$$ — количество чисел в перестановке, выписанной Васей ($$$1 \leq n \leq 500\,000$$$). В следующей строке находится $$$n$$$ целых чисел $$$next_1, next_2, \ldots, next_n$$$, разделенных пробелами ($$$next_i = -1$$$ или $$$i < next_i \leq n + 1$$$).

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$500\,000$$$.

Во взломах разрешается использовать только один тестовый случай, то есть $$$T = 1$$$.

Выходные данные

Выведите $$$T$$$ строк, в $$$i$$$-й ответ на $$$i$$$-й тестовый случай.

Если таких перестановок $$$p_1, p_2, \ldots, p_n$$$ чисел от $$$1$$$ до $$$n$$$, которые мог выписать Вася не существует, то выведите единственное число $$$-1$$$.

Иначе выведите $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$, разделённых пробелами ($$$1 \leq p_i \leq n$$$). Все определённые значения $$$next_i$$$, не равные $$$-1$$$, должны быть вычислены верно из перестановки $$$p_1, p_2, \ldots, p_n$$$ по определению из условия задачи. Если существует несколько таких перестановок, найдите любую.

Пример
Входные данные
6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5
Выходные данные
1 2 3
2 1
2 1 3
-1
1
3 2 1 4
Примечание

В первом тестовом случае для перестановки $$$p = [1, 2, 3]$$$ получится $$$next = [2, 3, 4]$$$, так как каждый элемент перестановки меньше следующего. Можно заметить, что это единственная подходящая перестановка.

Во третьем тестовом случае подойдет любая перестановка, так как все значения $$$next_i$$$ неизвестны.

В четвертом тестовом случае не существует ни одной подходящей перестановки, поэтому ответ $$$-1$$$.