测试数据来自 system/2928

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一个长为 \(N（2≤N≤10^5）\)的排列 \(p\)，包含从 \(1\) 到 \(N\) 的每个正整数恰好一次。然后进行如下操作：令 \(p\) 的剩余元素为 \(p_1′ ,p_2′ ,…,p_n′\)，如果 \(p_1′>p_n′\)，他写下 \(p_2′\) 并从排列中删除 \(p_1′\)。否则，他写下 \(p_{n−1}′\) 并从排列中删除 \(p_n′\) 。最终按顺序写下 \(N−1\) 个整数:\(h_1 ,h_2 ,…,h_{N−1}\) 。

　　现在给定 \(h\)，希望恢复原排列p，如果有多种可能，请输出字典序最小的。

【输入格式】

　　每组数据点包含 \(T（1≤T≤10）\) 组测试数据。每个组数据描述如下：第一行包含 \(N\)。第二行包含 \(N−1\) 个整数 \(h_1 ,h_2,…,h_{N−1} （1≤h_i≤N）\)。

【输出格式】

　　输出 \(T\) 行，每组数据输出一行。如果存在与 \(h\) 相一致的 \(1..N\) 的排列 \(p\)，输出字典顺序最小的 \(p\)。如果不存在这样的 \(p\)，输出 \(−1\)。

【输入输出样例】

　Input

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

　Output

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' = [1]\)
　　注意排列 \(p=[4,2,1,3]\) 也会产生同样的 \(h\)，但 \([3,1,2,4]\) 字典序更小。
　　对于第二组数据用例，不存在与 \(h\) 相一致的 \(p\)；\(p=[1,2]\) 和 \(p=[2,1]\) 均会产生 \(h=[1]\)，并非 \(h=[2]\)。

【测试点性质】

　　测试点 2：\(N≤8\)。
　　测试点 3−6：\(N≤100\)。
　　测试点 7−11：没有额外限制。

【来源】

　　Mr.he