2043: [USACO 2024 US Open Contest Bronze] Problem 3. Farmer John's Favorite Permutation

Farmer John has a permutation $p$ of length $N$ ($2\le N\le {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^{\prime },p_2^{\prime },\dots ,p_n^{\prime }$,

• If $p_1^{\prime }>p_n^{\prime }$, he writes down $p_2^{\prime }$ and removes $p_1^{\prime }$ from the permutation.
• Otherwise, he writes down $p_{n-1}^{\prime }$ and removes $p_n^{\prime }$ 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^{\prime }$, $p$ is lexicographically smaller than $p^{\prime }$ if $p_i<p_i^{\prime }$ at the first position $i$ where the two differ.

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$).

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

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