Farmer John 的排列重建问题

问题描述

Farmer John 有一个长度为 N（2 ≤ N ≤ $10^5$）的排列 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 个整数 $h_1$, $h_2$, …, $h_{N−1}$。给定 h，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 p，或者判断 Farmer Nhoj 一定犯了错误。我们知道，给定两个排列 p 和 p'，如果在第一个两者不同的位置 i 处有 $p_i$ < $p'_i$，则 p 的字典序小于 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。

样例

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' = [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：没有额外限制。

来源

一本通在线评测