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$$$,我们定义为$$$next_i = n + 1$$$。
晚上瓦夏放学回家,由于下雨,他的笔记本被淋湿了。现在无法读取一些书面数字。排列和一些值 $$$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$$$,他可以将其写入笔记本,并且所有不等于 $$$-1$$$ 的数字 $$$next_i$$$ 都是正确的。
输入
第一行包含一个整数 $$$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 < next_i \leq n + 1$$$)。
保证所有测试用例中$$$n$$$ 的总和不超过$$$500\,000$$$。
在 hacks 中你只能使用一个测试用例,所以 $$$T = 1$$$。
输出
打印 $$$T$$$ 行,其中第 $$$i$$$ 行回答第 $$$i$$$ 个测试用例。
如果 Vasya 不存在从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$,则打印唯一的数字 $$$-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$$$。如果存在多个解决方案,您可以找到其中任何一个。
示例
输入 #1
6 3 2 3 4 2 3 3 3 -1 -1 -1 3 3 4 -1 1 2 4 4 -1 4 5
输出 #1
1 2 3 2 1 2 1 3 -1 1 3 2 1 4
注意
在排列的第一个测试用例 $$$p = [1, 2, 3]$$$ Vasya 应该写 $$$next = [2, 3, 4]$$$,因为排列中的每个数字都小于下一个。很容易看出,这是唯一令人满意的排列。
在第三个测试用例中,任何排列都可以作为答案,因为所有数字 $$$next_i$$$ 都丢失了。
在第四个测试用例中,没有令人满意的排列,因此答案是 $$$-1$$$。