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

Polycarp 在白板上写下一个长度为 $n$ 的数组 $p$，该数组是 $1$ 到 $n$ 这些数的一个排列。换言之，$p$ 中每个从 $1$ 到 $n$ 的数恰好出现一次。

他还准备了一个结果数组 $a$，其初始为空（即长度为 $0$）。

随后，他恰好执行了 $n$ 步操作。每一步操作如下：

• 观察 $p$ 的最左端和最右端元素，并从中选出较小者；
• 若选出的是 $p$ 的最左端元素，则将其添加到 $a$ 的左侧；否则（即选出的是 $p$ 的最右端元素），则将其添加到 $a$ 的右侧；
• 将被选出的元素从 $p$ 中删除。

注意：在最后一步中，$p$ 的长度为 $1$，此时其唯一元素既是左端点也是右端点，因此该元素自然是最小值。此时 Polycarp 可自由决定该元素是添加到 $a$ 的左侧还是右侧。

我们来看一个例子：设 $n=4$，$p=[3, 1, 4, 2]$，初始时 $a=[]$。之后：

• 第一步：左右两端分别为 $3$ 和 $2$，较小者为右端的 $2$，因此此步后 $p=[3,1,4]$，$a=[2]$（将 $2$ 添加至右侧）；
• 第二步：左右两端分别为 $3$ 和 $4$，较小者为左端的 $3$，因此此步后 $p=[1,4]$，$a=[3,2]$（将 $3$ 添加至左侧）；
• 第三步：左右两端分别为 $1$ 和 $4$，较小者为左端的 $1$，因此此步后 $p=[4]$，$a=[1,3,2]$（将 $1$ 添加至左侧）；
• 第四步：$p$ 中仅剩 $4$，它同时是最左和最右元素。假设 Polycarp 选择将其添加至右侧，则此步后 $p=[]$，$a=[1,3,2,4]$（将 $4$ 添加至右侧）。

因此，经过 $n$ 步后，$a$ 的一种可能取值为 $a=[1,3,2,4]$。

现给你最终得到的数组 $a$，请找出任意一个可能的初始数组 $p$，使得按上述规则操作后能得到该 $a$；若不存在这样的 $p$，则判定无解。

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

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）——数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）——数组 $a$ 的元素。数组 $a$ 的所有元素互不相同。

保证所有测试用例的 $n$ 值之和不超过 $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.

输出 $t$ 行，每行包含对应输入数据组的答案：数字 $p_1, p_2, \dots, p_n$ —— 即数组 $p$ 的任意一种可能的初始取值，使得其最终得到给定的数组 $a$。$p$ 的所有元素均为 $1$ 到 $n$ 之间的互异整数。因此，若存在多个解，输出任意一个即可；若无解，则在该行输出 -1。

The first test case in the example is clarified in the main section of the problem statement. There may be other correct answers for this test set.

In the second test case, $n=1$. Thus, there is only one permutation that can be the answer: $p=[1]$. Indeed, this is the answer to this test case.

In the third test case of the example, no matter what permutation you take as $p$, after applying the $n$ steps, the result will differ from $a=[1, 3, 5, 4, 2]$.

示例中的第一个测试用例已在题目陈述的主部分中阐明。对于该测试集，可能存在其他正确的答案。

在第二个测试用例中，$n=1$。因此，唯一可能作为答案的排列是 $p=[1]$。事实上，这正是该测试用例的答案。

在示例的第三个测试用例中，无论你选取何种排列作为 $p$，经过 $n$ 步操作后，结果都将不同于 $a=[1, 3, 5, 4, 2]$。