#PU1421. USACO 2024 US Open Contest, Bronze — Problem 3. Farmer John's Favorite Permutation

USACO 2024 US Open Contest, Bronze — Problem 3. Farmer John's Favorite Permutation

USACO 2024 US Open Contest, Bronze — Problem 3. Farmer John's Favorite Permutation

题目描述

Farmer John has a permutation pp of length NN (2≤N≤105)2 \leq N \leq 10^5), containing each positive integer from 11 to NN exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled pp. To not be too cruel, FN has written some hints that will help FJ reconstruct pp. While there is more than one element remaining in pp, FN does the following: Let the remaining elements of pp be p1′,p2′,…,pn′p'_1, p'_2, \dots , p'_n, If p1′>pn′p'_1 > p'_n, he writes down p2′p'_2 and removes p1′p'_1 from the permutation. Otherwise, he writes down pn−1′p'_{n-1} and removes pn′p'_n from the permutation. At the end, Farmer Nhoj will have written down N−1N - 1 integers h1,h2,…,hN−1h_1, h_2, \dots, h_{N-1}, in that order. Given hh, Farmer John wants to enlist your help to reconstruct the lexicographically minimum pp consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations pp and p′p', pp is lexicographically smaller than p′p' if pi<pi′p_i < p'_i at the first position ii where the two differ.

输入格式

Each input consists of TT independent test cases (1≤T≤101\le T\le 10). Each test case is described as follows: The first line contains NN. The second line contains N−1N - 1 integers h1,h2,…,hN−1h_1, h_2, \dots, h_{N-1} (1≤hi≤N1\le h_i\le N).

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
For the fourth test case, if $p=[3,1,2,4]$ then FN will have written down
$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]

提示

[3,1,2,4][3,1,2,4] is lexiocgraphically smaller. For the second test case, there is no pp consistent with hh; both p=[1,2]p=[1,2] and p=[2,1]p=[2,1] would produce h=[1]h=[1], not h=[2]h=[2].