# [Solution] Polycarp Recovers the Permutation solution codeforces

## Polycarp Recovers the Permutation solution codeforces

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

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

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 11 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).

Also read: ATM and Students solution codeforces

### Polycarp Recovers the Permutation solution codeforces

Let’s look at an example. Let 𝑛=4n=4𝑝=[3,1,4,2]p=[3,1,4,2]. Initially 𝑎=[]a=[]. Then:

• During the first step, the minimum is on the right (with a value of 22), so after this step, 𝑝=[3,1,4]p=[3,1,4] and 𝑎=[2]a=[2] (he added the value 22 to the right).
• During the second step, the minimum is on the left (with a value of 33), so after this step, 𝑝=[1,4]p=[1,4] and 𝑎=[3,2]a=[3,2] (he added the value 33 to the left).
• During the third step, the minimum is on the left (with a value of 11), so after this step, 𝑝=[4]p=[4] and 𝑎=[1,3,2]a=[1,3,2] (he added the value 11 to the left).
• During the fourth step, the minimum is both left and right (this value is 44). Let’s say Polycarp chose the right option. After this step, 𝑝=[]p=[] and 𝑎=[1,3,2,4]a=[1,3,2,4] (he added the value 44 to the right).

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

Also read: Make Even solution codeforces

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.

Input Polycarp Recovers the Permutation solution codeforces

The first line of the input contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases in the test.

Each test case consists of two lines. The first of them contains an integer 𝑛n (1𝑛21051≤n≤2⋅105) — the length of the array 𝑎a. The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤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 21052⋅105.

Output Polycarp Recovers the Permutation solution codeforces

Print 𝑡t lines, each of the lines must contain the answer to the corresponding set of input data: numbers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn  — 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 11 to 𝑛n. Thus, if there are several solutions, print any. If there is no solution, then print -1 on the line.

Example Polycarp Recovers the Permutation solution codeforces

input

Copy
4
4
1 3 2 4
1
1
5
1 3 5 4 2
3
3 2 1


output

Copy
3 1 4 2
1
-1
2 3 1

Note

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, 𝑛=1n=1. Thus, there is only one permutation that can be the answer: 𝑝=[1]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 𝑎=[1,3,5,4,2]a=[1,3,5,4,2].