4031. [USACO24 Open Bronze]Farmer John’s Favorite Permutation

【题目描述】

$Farmer$ $John$ 有一个长为 $N$（$2\le N \le 10^5$）的排列 $p$，包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而，$Farmer$ $Nhoj$ 闯入了 $FJ$ 的牛棚并拆散了 $p$。为了不至于太过残忍，$FN$ 写了一些能够帮助 $FJ$ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时，$FN$ 会执行以下操作：

令 $p$ 的剩余元素为 $p_1^\prime,p_2^\prime,\ldots,p_n^\prime$，

$\bullet$ 如果 $p_1^\prime>p_n^\prime$，他写下 $p_2^\prime$ 并从排列中删除 $p_1^\prime$。

$\bullet$ 否则，他写下 $p_{n−1}^\prime$ 并从排列中删除 $p_n^\prime$。

最终，$Farmer$ $Nhoj$ 将按顺序写下 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$。给定 $h$，$Farmer$ $John$

希望得到你的帮助重建与 $Farmer$ $Nhoj$ 的提示相一致的最小字典序 $p$，或者判断 $Farmer Nhoj$

一定犯了错误。我们知道，给定两个排列 $p$ 和 $p^\prime$，如果在第一个两者不同的位置 $i$ 处有

$p_i<p_i^\prime$，则 $p$ 的字典序小于 $p^\prime$。

【输入格式】

每个测试点包含 $T$ 个独立的测试用例（$1\le T\le 10$）。每个测试用例的描述如下：

第一行包含 $N$。

第二行包含 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$（$1\le h_i\le N$）。

【输出格式】

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

如果存在与 $h$ 相一致的 $1\ldots N$ 的排列 $p$，输出字典顺序最小的 $p$。如果不存在这样的 $p$，输出 $-1$。

【样例1输入】

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

【样例1输出】

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

【样例1说明】

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

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

$p_1' < p_n'\Rightarrow h_1 = 2$

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

$p_1' > p_n' \Rightarrow h_2 = 1$

$p' = [1,2]$

$p_1' < p_n' \Rightarrow 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输入输出】

点击下载样例2 

【数据规模与约定】

$\bullet$ 测试点 $1$：$N\le 8$。

$\bullet$ 测试点 $2-5$：$N\le 100$。

$\bullet$ 测试点 $6-10$：没有额外限制。

【来源】

USACO