题目描述

Farmer John 有一个长为 $N$ 的排列 $p$，包含从$1$到$N$ 的每个正整数恰好一次。然而，farmer Nhoj闯入了FJ 的牛棚并拆散了 $p$。

为了不至于太过残忍，$FN$ 写了一些能够帮助$FJ$重建$p$的提示。当$p$中剩余多于一个元素时，$FN$ 会执行以下操作:

令$p$的剩余元素为 $p'_1,p'_2,，..,p'_n$

如果$p'_1>p'_n$,，他写下 $p'_2$ 并从排列中删除 $p'_1$.

否则，他写下 $p'_{n-1}$并从排列中删除 $p'_n$。

最终，Farmer Nhoj将按顺序写下 $N -1$个整数 $h1,h2,…….,h_{N-1}$。给定 $h$，FarmerJohn 希望得到你的帮助重建与Farmer Nhoj的提示相一致的最小字典序$p$，或者判断 Farmer Nho 一定犯了错误。

我们知道，给定两个排列$p$和$p'$,如果在第一个两者不同的位置$i$处有 $p_i < p'_i$,，则$p$的字典序小于 $p'$。

提示

每个测试点包含 $T$ 个独立的测试用例。

每个测试用例的描述如下:

第一行包含 $N$。

第二行包含 $N -1$个整数 $h_1,h_2,...,h_{N-1}$。

输出

输出 $T$ 行，每个测试用例一行

如果存在与$h$ 相一致的 $1...N$ 的排列 $p$，输出字典顺序最小的 $p$。

如果不存在这样的$p$，输出 -1。

5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1

1 2
-1
-1
3 1 2 4
1 2 3 4

样例解释

对于第四个测试用例，如果$p=[3,1,2,4]$则 FN 将写下 $h =[2,1,1]$。

$p'=[3,1,2,4]$

$p'_1<p'_n \ -> \ h_1=2$

$p'=[3,1,2]$

$p'_1>p'_n \ -> \ h_2=1$

$p'=[1,2]$ $p'_1<p'_n \ -> \ h_3=1$

注意排列 $p =[4,2,1,3]$也会产生同样的 $h$，但$[3,1,2,4]$字典序更小。

对于第二个测试用例，不存在与ん相一致的 $p$;$p= [1,2]$和$p=[2,1]$均会产生$h = [1]$，并非$h =[2]$。

提示

测试点 2:$N < 8$

测试点3-6:$N < 100。$

测试点7-11:

$2 \leq N \leq 10^5$

$1 \leq T \leq 10$

$1 \leq h_i \leq N$