{"problem":{"name":"[USACO24OPEN] Farmer John's Favorite Permutation B","description":{"content":"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 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10276"},"statements":[{"statement_type":"Markdown","content":"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:  \n\nLet the remaining elements of $p$ be $p'_1, p'_2, \\dots , p'_n$, \n-  If $p'_1 > p'_n$, he writes down $p'_2$ and removes $p'_1$ from the permutation.\n-  Otherwise, he writes down $p'_{n-1}$ and removes $p'_n$ from the permutation.  \n\nAt 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.\n\n## Input\n\nEach input consists of $T$ independent test cases ($1\\le T\\le 10$). Each test case is described as follows:  \n\nThe first line contains $N$.  \n\nThe second line contains $N - 1$ integers $h_1, h_2, \\dots, h_{N-1}$ ($1\\le h_i\\le N$).\n\n## Output\n\nOutput $T$ lines, one for each test case.  \n\nIf 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$.\n\n[samples]\n\n## Note\n\nFor the fourth test case, if $p=[3,1,2,4]$ then FN will have written down $h=[2,1,1]$.  \n```text\np' = [3,1,2,4]\np_1' < p_n' -> h_1 = 2\np' = [3,1,2]\np_1' > p_n' -> h_2 = 1\np' = [1,2]\np_1' < p_n' -> h_3 = 1\np' = [1]\n```\n\nNote that the permutation $p=[4,2,1,3]$ would also produce the same $h$, but $[3,1,2,4]$ is lexiocgraphically smaller.  \n\nFor 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]$.  \n\n#### SCORING:\n\n- Input 2: $N\\le 8$\n- Inputs 3-6: $N\\le 100$\n- Inputs 7-11: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10276","tags":["数学","USACO","2024"],"sample_group":[["5\n2\n1\n2\n2\n4\n1 1 1\n4\n2 1 1\n4\n3 2 1","1 2\n-1\n-1\n3 1 2 4\n1 2 3 4"]],"created_at":"2026-03-03 11:09:25"}}