记录编号	596193	评测结果	AAAAAAAAAA
题目名称	[USACO24 Open Bronze]Farmer John’s Favorite Permutation	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	1.048 s
提交时间	2024-10-23 11:46:16	内存使用	5.10 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,h[100010],b[100010],a[100010],in[100010];
void chu()
{
	memset(b,0,sizeof(b));
	memset(in,0,sizeof(in));
	memset(a,0,sizeof(a));
	memset(h,0,sizeof(h));
}
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d",&h[i]);
		b[h[i]]++;
	}
	if(h[n-1]!=1)
	{
		printf("-1\n");
		return;
	}
	if(b[1]>2)
	{
		printf("-1\n");
		return;
	}
	int bj1=0,bj2=0;
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0)
		{
			if(bj1) bj2=i;
			else bj1=i;
		}
		if(b[i]>1&&i!=1)
		{
			printf("-1\n");
			return;
		}
	}
	if(bj1>bj2) swap(bj1,bj2);
	if(bj1==0) bj1=1;
	a[1]=bj1;
	a[n]=bj2;
	in[bj1]=1;
	in[bj2]=1;
	int l=1,r=n,now=1;
	for(int i=3;i<=n;i++)
	{
		if(a[l]>a[r])
		{
			while(in[h[now]]) now++;
			l++;
			a[l]=h[now];
			in[h[now]]=1;
		}
		else
		{
			while(in[h[now]]) now++;
			r--;
			a[r]=h[now];
			in[h[now]]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
	return;
}
int main()
{
	freopen("permutation.in","r",stdin);
    freopen("permutation.out","w",stdout);
	scanf("%d",&t);
	while(t--)
	{
		chu();
		solve();
	} 
	return 0;
}