Codeforces Round #756 (Div. 3) C. Polycarp Recovers the Permutation

Codeforces Round #756 (Div. 3) C. Polycarp Recovers the Permutation

题目链接：Problem - C - Codeforces

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

He also prepared a resulting array aa, 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 aa both on the left and on the right (at the discretion of Polycarp).

Let's look at an example. Let n=4n=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 11), 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 aa after nn steps could be a=[1,3,2,4].

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

Input

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

Each test case consists of two lines. The first of them contains an integer nn (1≤n≤2⋅105) — the length of the array aa. The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n) — the elements of the array aa. All elements of the aa array are distinct numbers.

It is guaranteed that the sum of the values nn over all test cases in the test does not exceed 2⋅105.

Output

Print tt lines, each of the lines must contain the answer to the corresponding set of input data: numbers p1,p2,…,pn  — any of the possible initial values of the array pp, which will lead to the given array aa. All elements of pp are distinct integers from 1 to nn. Thus, if there are several solutions, print any. If there is no solution, then print -1 on the line.

Example

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, n=1. Thus, there is only one permutation that can be the answer: p=[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 nn steps, the result will differ from a=[1,3,5,4,2].

题意：将p数组的左右两端点比较，左边大从a的左边压入，反之从右边压入，然后删除当前位置，最后一位可以从任意位置压入，然后题目给出a数组，问如何构造p数组，如果没有输出-1

思路：最大的数组肯定在a数组的两端，如果不是就无法构造，输出-1

我们通过最大的位置来确定他在p数组的位置，如果在a的最左边那就在p的最左边，反之亦然

然后通过规则一步一步构造

#include
using namespace std;

int arr[200005];
int p[200005];

int main(){
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	int n;
	while(t--){
		cin >> n;
		int maxn = 0;
		for(int i = 1; i <= n; i++){
			cin >> arr[i];
			maxn = max(maxn, arr[i]);
		}
		if(arr[1] != maxn && arr[n] != maxn){
			cout << -1 << endl;
			continue;
		}
		int ans;
		if(arr[1] == maxn){
			p[1] = maxn;
			ans =  2;
			for(int i = n; i >= 2; i--){
				p[ans++] = arr[i];
			}
		}else{
			p[n] = maxn;
			ans = 1;
			for(int i = n - 1; i >= 1; i--){
				p[ans++] = arr[i];
			}
		}
		for(int i = 1; i <= n; i++){
			if(i != 1){
				cout << " ";
			}
			cout << p[i];
		}
		cout << endl;
	}
	return 0;
}