Farmer John's Favorite Permutation 1s 1024MB

Problems

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.

Input

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

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.

Subtask

#	Score	Condition
#1	20	N \le 8
#2	30	N \le 100
#3	50	추가 제약 조건 없음

Example

5keyboard_return
2keyboard_return
1keyboard_return
2keyboard_return
2keyboard_return
4keyboard_return
1space_bar 1space_bar 1keyboard_return
4keyboard_return
2space_bar 1space_bar 1keyboard_return
4keyboard_return
3space_bar 2space_bar 1

1space_bar 2keyboard_return
-1keyboard_return
-1keyboard_return
3space_bar 1space_bar 2space_bar 4keyboard_return
1space_bar 2space_bar 3space_bar 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].

Tag

Source

USACO 2024 US Open Bronze

You must sign in to write code.

#8170 upload 1 done 1 how_to_reg 1 call_split Subtask

Farmer John's Favorite Permutation timer 1s memory 1024MB

Problems text_fields