Farmer John's Favorite Permutation
Farmer John has a permutation p of length N (2≤N≤105), 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 p1′,p2′,…,pn′,
- If p1′>pn′, he writes down p2′ and removes p1′ from the permutation.
- Otherwise, he writes down pn−1′ and removes pn′ from the permutation.
At the end, Farmer Nhoj will have written down N−1 integers h1,h2,…,hN−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 pi<pi′ at the first position i where the two differ.
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].
SCORING:
- Input 2: N≤8
- Inputs 3-6: N≤100
- Inputs 7-11: No additional constraints.
Problem credits: Chongtian Ma
Source: USA Computing Olympiad.
Input Format
Each input consists of T independent test cases (1≤T≤10). Each test case is described as follows:
The first line contains N.
The second line contains N−1 integers h1,h2,…,hN−1 (1≤hi≤N).
Output Format
Output T lines, one for each test case.
If there is a permutation p of 1…N consistent with h, output the lexicographically smallest such p. If no such p exists, output −1.