| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 156 | 50 | 45 | 39.823% |
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,ドル
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$.
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]$.