Polycarp 在白板上写下了一个长度为 $$$n$$$ 的数组 $$$p$$$,它是从 $$$1$$$ 到 $$$n$$$ 的数字排列。换句话说,在 $$$p$$$ 中,从 $$$1$$$ 到 $$$n$$$ 的每个数字恰好出现一次。
他还准备了一个结果数组$$$a$$$,该数组最初是空的(也就是说,它的长度为$$$0$$$)。
之后,他精确地执行了 $$$n$$$ 步。每一步看起来都是这样的:
- 查看 $$$p$$$ 最左边和最右边的元素,并选择两者中较小的一个。
- 如果您选择了 $$$p$$$ 最左边的元素,请将其附加到 $$$a$$$ 的左侧;否则,如果您选择了 $$$p$$$ 最右边的元素,请将其附加到 $$$a$$$ 的右侧。
- 选取的元素将从 $$$p$$$ 中删除。
请注意,在最后一步中,$$$p$$$ 的长度为$$$1$$$,并且其最小元素既是最左边的,也是最右边的。在这种情况下,坡旅甲可以选择最小元素所扮演的角色。换句话说,这个元素可以添加到 $$$a$$$ 的左侧和右侧(由 Polycarp 自行决定)。
让我们看一个例子。设 $$$n=4$$$,$$$p=[3, 1, 4, 2]$$$。最初$$$a=[]$$$。然后:
- 在第一步中,最小值在右侧(值为 $$$2$$$),因此在这一步之后,$$$p=[3,1,4]$$$ 和 $$$a=[2]$$$ (他将值 $$$2$$$ 添加到右侧)。
- 在第二步中,最小值在左侧(值为$$$3$$$),因此在这一步之后,$$$p=[1,4]$$$ 和 $$$a=[3,2]$$$ (他将值$$$3$$$ 添加到左侧)。
- 在第三步中,最小值在左侧(值为$$$1$$$),因此在这一步之后,$$$p=[4]$$$ 和 $$$a=[1,3,2]$$$ (他将值$$$1$$$ 添加到左侧)。
- 在第四步中,最小值是左和右(该值为$$$4$$$)。假设波利卡普选择了正确的选项。这一步之后,$$$p=[]$$$ 和$$$a=[1,3,2,4]$$$(他在右边添加了值$$$4$$$)。
因此,在$$$n$$$步骤之后$$$a$$$的可能值可以是$$$a=[1,3,2,4]$$$。
您将获得结果数组 $$$a$$$ 的最终值。查找 $$$p$$$ 的任何可能的初始值,该初始值可以产生给定的 $$$a$$$,或者确定没有解决方案。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
每个测试用例由两行组成。第一个包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 数组 $$$a$$$ 的长度。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。 $$$a$$$ 数组的所有元素都是不同的数字。
保证测试中所有测试用例的值 $$$n$$$ 之和不超过 $$$2\cdot10^5$$$。
输出
打印 $$$t$$$ 行,每行必须包含相应输入数据集的答案:数字 $$$p_1, p_2, \dots, p_n$$$ — 数组 $$$p$$$ 的任何可能的初始值,这将导致给定数组 $$$a$$$。 $$$p$$$ 的所有元素都是从 $$$1$$$ 到 $$$n$$$ 的不同整数。因此,如果有多个解决方案,则打印任何一个。如果无解,则在该行打印-1。
示例
输入 #1
4 4 1 3 2 4 1 1 5 1 3 5 4 2 3 3 2 1
输出 #1
3 1 4 2 1 -1 2 3 1
注意
示例中的第一个测试用例在问题陈述的主要部分中进行了澄清。该测试集可能还有其他正确答案。
在第二个测试用例中,$$$n=1$$$。因此,只有一种排列可以作为答案:$$$p=[1]$$$。事实上,这就是这个测试用例的答案。
在示例的第三个测试用例中,无论 $$$p$$$ 采用什么排列,在应用 $$$n$$$ 步骤后,结果都将与 $$$a=[1, 3, 5, 4, 2]$$$ 不同。