Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

K. Peak-a-boo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$p$$$ be an array, initially a permutation$$$^{\text{∗}}$$$ of the integers from $$$1$$$ to $$$n$$$. An array-processing machine produces a sequence $$$s$$$ by repeating the following steps exactly $$$n-1$$$ times:

  1. Identify all peaks of the current array $$$p$$$. An element $$$p_i$$$ (where $$$1 \le i \le |p|$$$) is a peak if it is strictly greater than its existing adjacent elements; formally, $$$p_i \gt p_{i-1}$$$ (when $$$i \gt 1$$$) and $$$p_i \gt p_{i+1}$$$ (when $$$i \lt |p|$$$).
  2. Among all peaks, take the one with the smallest value.
  3. Append that value to $$$s$$$.
  4. Remove that element from $$$p$$$, shifting every later element one position to the left to close the gap.

The process stops when a single element remains in $$$p$$$.

You are given a sequence $$$s$$$ of $$$n-1$$$ integers. Determine whether some initial permutation of length $$$n$$$ produces exactly $$$s$$$. If one exists, construct any such permutation; otherwise, report that it is impossible.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation, and $$$[1,3,4]$$$ is also not a permutation.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the initial permutation.

The second line contains $$$n-1$$$ integers $$$s_1, s_2, \ldots, s_{n-1}$$$ ($$$1 \le s_i \le n$$$) — the elements of the sequence $$$s$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ space-separated integers — any permutation of length $$$n$$$ that the machine turns into $$$s$$$. If several such permutations exist, print any of them. If none exists, print -1.

Example
Input
2
6
3 5 4 6 2
2
1
Output
6 2 5 4 1 3
-1
Note

In the first test case, one valid initial permutation is $$$[6, 2, 5, 4, 1, 3]$$$. The machine processes it as follows, with the removed peak shown in bold:

  • $$$[6, 2, 5, 4, 1, \mathbf{3}]$$$ — the smallest peak is $$$3$$$.
  • $$$[6, 2, \mathbf{5}, 4, 1]$$$ — the smallest peak is $$$5$$$.
  • $$$[6, 2, \mathbf{4}, 1]$$$ — the smallest peak is $$$4$$$.
  • $$$[\mathbf{6}, 2, 1]$$$ — the smallest peak is $$$6$$$.
  • $$$[\mathbf{2}, 1]$$$ — the smallest peak is $$$2$$$.

This yields $$$s = [3, 5, 4, 6, 2]$$$.

In the second test case, no valid permutation of length $$$2$$$ can produce $$$s= [1]$$$.