CF1158C Permutation recovery

Vasya 写下了一个由 $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 < j \leq n$ 且 $p_j > p_i$ 的最小下标 $j$。如果不存在这样的 $j$，则定义 $next_i = n + 1$。 傍晚放学回家时，Vasya 的笔记本被雨淋湿了，现在有些数字已经无法辨认。排列和一些 $next_i$ 的值完全丢失！如果某个 $i$ 的 $next_i$ 丢失了，则记 $next_i = -1$。 现在给定 $next_1, next_2, \ldots, next_n$（其中有些可能等于 $-1$）。请你帮助 Vasya 找出一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$，使得他可以把它写在笔记本上，并且所有 $next_i \neq -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$。 在 hack 数据中只能使用一个测试用例，即 $T = 1$。

输出 $T$ 行，第 $i$ 行为第 $i$ 个测试用例的答案。 如果不存在满足条件的排列 $p_1, p_2, \ldots, p_n$，则输出 $-1$。 否则输出 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$，用空格分隔（$1 \leq p_i \leq n$）。所有 $next_i \neq -1$ 的位置都要满足题目中的定义。如果有多组解，输出任意一组均可。

在第一个测试用例中，对于排列 $p = [1, 2, 3]$，Vasya 应该写下 $next = [2, 3, 4]$，因为排列中的每个数都小于其后面的数。显然这是唯一满足条件的排列。 在第三个测试用例中，所有 $next_i$ 都丢失了，因此任意一个排列都可以作为答案。 在第四个测试用例中，不存在满足条件的排列，因此答案为 $-1$。 由 ChatGPT 4.1 翻译