A14721 | Polycarp Recovers the Permutation

Polycarp wrote on a whiteboard an array $p$ of length $n$ , which is a permutation of numbers from $1$ to $n$ . In other words, in $p$ each number from $1$ to $n$ occurs exactly once.

He also prepared a resulting array $a$ , which is initially empty (that is, it has a length of $0$ ).

After that, he did exactly $n$ steps. Each step looked like this:

- Look at the leftmost and rightmost elements of $p$ , and pick the smaller of the two.
- If you picked the leftmost element of $p$ , append it to the left of $a$ ; otherwise, if you picked the rightmost element of $p$ , append it to the right of $a$ .
- The picked element is erased from $p$ .

Note that on the last step, $p$ has a length of $1$ and its minimum element is both leftmost and rightmost. In this case, Polycarp can choose what role the minimum element plays. In other words, this element can be added to $a$ both on the left and on the right (at the discretion of Polycarp).

Let's look at an example. Let $n=4$ , $p=[3, 1, 4, 2]$ . Initially $a=[]$ . Then:

- During the first step, the minimum is on the right (with a value of $2$ ), so after this step, $p=[3,1,4]$ and $a=[2]$ (he added the value $2$ to the right).
- During the second step, the minimum is on the left (with a value of $3$ ), so after this step, $p=[1,4]$ and $a=[3,2]$ (he added the value $3$ to the left).
- During the third step, the minimum is on the left (with a value of $1$ ), so after this step, $p=[4]$ and $a=[1,3,2]$ (he added the value $1$ to the left).
- During the fourth step, the minimum is both left and right (this value is $4$ ). Let's say Polycarp chose the right option. After this step, $p=[]$ and $a=[1,3,2,4]$ (he added the value $4$ to the right).

Thus, a possible value of $a$ after $n$ steps could be $a=[1,3,2,4]$ .

You are given the final value of the resulting array $a$ . Find any possible initial value for $p$ that can result the given $a$ , or determine that there is no solution.

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

Each test case consists of two lines. The first of them contains an integer $n$ ( $1 \le n \le 2\cdot10^5$ ) — the length of the array $a$ . The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le n$ ) — the elements of the array $a$ . All elements of the $a$ array are distinct numbers.

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

Print $t$ lines, each of the lines must contain the answer to the corresponding set of input data: numbers $p_1, p_2, \dots, p_n$ — any of the possible initial values of the array $p$ , which will lead to the given array $a$ . All elements of $p$ are distinct integers from $1$ to $n$ . Thus, if there are several solutions, print any. If there is no solution, then print -1 on the line.