페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8170
서브태스크

Farmer John's Favorite Permutation 1s 1024MB

문제

Farmer John has a permutation p of length N (2 \leq N \leq 10^5), containing each positive integer from 1 to N exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled p. To not be too cruel, FN has written some hints that will help FJ reconstruct p. While there is more than one element remaining in p, FN does the following:

Let the remaining elements of p be p'_1, p'_2, \dots , p'_n,

  • If p'_1 > p'_n, he writes down p'_2 and removes p'_1 from the permutation.

  • Otherwise, he writes down p'_{n-1} and removes p'_n from the permutation.

At the end, Farmer Nhoj will have written down N - 1 integers h_1, h_2, \dots, h_{N-1}, in that order. Given h, Farmer John wants to enlist your help to reconstruct the lexicographically minimum p consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations p and p', p is lexicographically smaller than p' if p_i < p'_i at the first position i where the two differ.


입력

Each input consists of T independent test cases (1\le T\le 10). Each test case is described as follows:

The first line contains N.

The second line contains N - 1 integers h_1, h_2, \dots, h_{N-1} (1\le h_i\le N).


출력

Output T lines, one for each test case.

If there is a permutation p of 1\dots N consistent with h, output the lexicographically smallest such p. If no such p exists, output -1.


부분문제

번호 점수 조건
#120점

N \le 8

#230점

N \le 100

#350점

추가 제약 조건 없음


예제 

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]

Note that the permutation p=[4,2,1,3] would also produce the same h, but [3,1,2,4] is lexiocgraphically smaller.

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



출처

USACO 2024 US Open Bronze

로그인해야 코드를 작성할 수 있어요.