Processing math: 100%

USACO 2024 US Open Contest, Bronze

Problem 3. Farmer John's Favorite Permutation


Contest has ended.

Log in to allow submissions in analysis mode


Farmer John has a permutation p of length N (2N105), 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 pn1 and removes pn from the permutation.

At the end, Farmer Nhoj will have written down N1 integers h1,h2,,hN1, 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.

INPUT FORMAT (input arrives from the terminal / stdin):

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

The first line contains N.

The second line contains N1 integers h1,h2,,hN1 (1hiN).

OUTPUT FORMAT (print output to the terminal / stdout):

Output T lines, one for each test case.

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

SAMPLE INPUT:

5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1

SAMPLE OUTPUT:

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].

SCORING:

  • Input 2: N8
  • Inputs 3-6: N100
  • Inputs 7-11: No additional constraints.

Problem credits: Chongtian Ma

Contest has ended. No further submissions allowed.