USACO 2024 US Open Contest, Bronze

Problem 3. Farmer John's Favorite Permutation

Farmer John有一个长度为$N$（$2 \leq N \leq 10^5$）的排列$p$，其中包含从$1$到$N$的每个正整数恰好一次。然而，Farmer Nhoj闯入了FJ的谷仓并打乱了$p$。为了不太残忍，FN写下了一些提示来帮助FJ重建$p$。当$p$中还有多个元素时，FN执行以下操作： 设$p$的剩余元素为$p'_1, p'_2, \dots, p'_n$， 如果$p'_1 > p'_n$，他写下$p'_2$并从排列中移除$p'_1$。 否则，他写下$p'_{n - 1}$并从排列中移除$p'_n$。 最后，Farmer Nhoj将按顺序写下$N - 1$个整数$h_1, h_2, \dots, h_{N - 1}$。给定$h$，Farmer John希望你帮助重建与Farmer Nhoj的提示一致的字典序最小的$p$，或者确定Farmer 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$行，每个测试用例一行。 如果存在与$h$一致的$1\dots 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\le 8$
• 输入3 - 6：$N\le 100$
• 输入7 - 11：无额外限制。

问题提供者：Chongtian Ma