本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

农夫 John 有一个长度为 $N$ 的排列 $p$（$2 \leq N \leq 10^5$），其中恰好包含从 $1$ 到 $N$ 的每个正整数各一次。然而，农夫 Nhoj 闯入了 FJ 的谷仓并把 $p$ 拆散了。为了不至于太残忍，FN 写下了一些提示来帮助 FJ 重新构造 $p$。当 $p$ 中剩余元素数量大于 1 时，FN 会执行如下操作： 设当前剩余的 $p$ 的元素为 $p'_1, p'_2, \dots , p'_n$。 如果 $p'_1 > p'_n$，他会写下 $p'_2$，并从排列中移除 $p'_1$。 否则，他会写下 $p'_{n-1}$，并从排列中移除 $p'_n$。 最后，农夫 Nhoj 将按顺序写下 $N - 1$ 个整数 $h_1, h_2, \dots, h_{N-1}$。给定 $h$，农夫 John 希望你帮助他重构与农夫 Nhoj 提示一致的、字典序最小的排列 $p$，或者判断农夫 Nhoj 一定是弄错了。回顾：给定两个排列 $p$ 与 $p'$，若在它们首次出现不同的下标 $i$ 处有 $p_i < p'_i$，则称 $p$ 的字典序小于 $p'$。

输入格式

每个输入包含 $T$ 个相互独立的测试用例（$1\le T\le 10$）。每个测试用例如下： 第一行包含 $N$。 第二行包含 $N - 1$ 个整数 $h_1, h_2, \dots, h_{N-1}$（$1\le h_i\le N$）。

输出格式

输出 $T$ 行，每行对应一个测试用例。 如果存在一个由 $1\dots N$ 组成且与 $h$ 一致的排列 $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]$。 SCORING: Input 2: $N\le 8$ Inputs 3-6: $N\le 100$ Inputs 7-11: 无额外限制。 题目鸣谢：Chongtian Ma

来源

USACO|2024|Bronze