记录编号	596201	评测结果	AAAAAAAAAA
题目名称	[USACO24 Open Bronze]Farmer John’s Favorite Permutation	最终得分	100
用户昵称	Davinci	是否通过	通过
代码语言	C++	运行时间	1.939 s
提交时间	2024-10-23 14:50:05	内存使用	4.56 MiB

#include<bits/stdc++.h>
using namespace std;
int h[100005];
int v[100005];
int a[100005];
bool in[100005];
void niu(){
	memset(v,0,sizeof v);
	memset(in,0,sizeof in);
	memset(a,0,sizeof a);
	memset(h,0,sizeof h);
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++){
		cin>>h[i];
		v[h[i]]++;
	}
	if(h[n-1]!=1){
		cout<<-1<<endl;
		return;
	}
	int x1=0,x2=0;
	for(int i=1;i<=n;i++){
		if(v[i]==0){
			if(x1){
				x2=i;			
			}else{
				x1=i;
			}
		}if(v[i]>1&&i>1||v[i]>2){
			cout<<-1<<endl;
			return;
		}
	}
	if(x1>x2){
		swap(x1,x2);
	}
	if(x1==0){
		x1=1;	
	}
	int l=1,r=n;
	a[l]=x1;
	a[r]=x2;
	in[x1]=in[x2]=1;
	int nw=1;
	for(int i=1;i<=n-1;i++){
		if(r==l+1){
			break;
		}
		if(a[l]<a[r]){
			a[r-1]=h[i];
			r--;
		}else{
			a[l+1]=h[i];
			l++;
		}	
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl; 
}
int main(){
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		niu(); 
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}