Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3) B. Box 贪心

B. Box

Permutation p is a sequence of integers p=[p1,p2,…,pn], consisting of n distinct (unique) positive integers between 1 and n, inclusive. For example, the following sequences are permutations: [3,4,1,2], [1], [1,2]. The following sequences are not permutations: [0], [1,2,1], [2,3], [0,1,2].

The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation p of length n.

You don't know this permutation, you only know the array q of prefix maximums of this permutation. Formally:

q1=p1,

q2=max(p1,p2),

q3=max(p1,p2,p3),

...

qn=max(p1,p2,…,pn).

You want to construct any possible suitable permutation (i.e. any such permutation, that calculated q for this permutation is equal to the given array).

Input

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

The first line of a test case contains one integer n (1≤n≤105) — the number of elements in the secret code permutation p.

The second line of a test case contains n integers q1,q2,…,qn (1≤qi≤n) — elements of the array q for secret permutation. It is guaranteed that qi≤qi+1 for all i (1≤i<n).

The sum of all values n over all the test cases in the input doesn't exceed 105.

Output

For each test case, print:

If it's impossible to find such a permutation p, print "-1" (without quotes).

Otherwise, print n distinct integers p1,p2,…,pn (1≤pi≤n). If there are multiple possible answers, you can print any of them.

Example

input

4

5

1 3 4 5 5

4

1 1 3 4

2

2 2

1

1

output

1 3 4 5 2

-1

2 1

1

Note

In the first test case of the example answer [1,3,4,5,2] is the only possible answer:

q1=p1=1;

q2=max(p1,p2)=3;

q3=max(p1,p2,p3)=4;

q4=max(p1,p2,p3,p4)=5;

q5=max(p1,p2,p3,p4,p5)=5.

It can be proved that there are no answers for the second test case of the example.

题意

现在给你前缀最大值是多少，让你还原这个排列，问你是否有解。

题解

给了你前缀最大值，我们现在如果发现前缀最大值变化了，那么这个位置肯定是这个最大值，否则就插入了一个小的数，那么我们插入最小的就好。

代码

#include<bits/stdc++.h>

using namespace std;

vector<int>Q;

void solve(){

	int n;scanf("%d",&n);

	Q.clear();

	vector<int> ans;

	set<int>S;

	for(int i=0;i<n;i++){

		int x;scanf("%d",&x);

		Q.push_back(x);

		S.insert(i+1);

	}

	int mx = 0;

	for(int i=0;i<n;i++){

		if(Q[i]>mx){

			if(S.count(Q[i])){

				S.erase(Q[i]);

				ans.push_back(Q[i]);

			}else{

				cout<<"-1"<<endl;

				return;

			}

			mx = Q[i];

		}else{

			if(*S.begin()>mx){

				cout<<"-1"<<endl;

				return;

			}else{

				ans.push_back(*S.begin());

				S.erase(S.begin());

			}

		}

	}

	for(int i=0;i<ans.size();i++){

		cout<<ans[i]<<" ";

	}

	cout<<endl;

}

int main(){

	int t;

	scanf("%d",&t);

	while(t--){

		solve();

	}

}

巴特西