每次去掉两个中更大的一个数，最后必然剩下 $1$，所以 $h_{n-1}$ 必须为 $1$，否则无解。

$1$ 最多只会被输出两次，即左边删掉的一次和右边删掉的一次。如果有超过两次则也无解。

其它数最多只会被输出一次，因为另一边有一个 $1$ 挡着呢。如果一个非 $1$ 的数被输出两次，则也无解。

无解的情况分析完了，那么怎么构造呢？

注意到刚开始在最两边的数（如果不是 $1$）不会被输出。可以把不出现的的两个数（或者一个数，如果 $1$ 只出现了一次）挑出来，先放到数列的两端。要求字典序最小的方案，则将更小的那个安排在前面。如果只有一个数没被输出，说明 $1$ 在数列的最前面。

接下来按 $h$ 数组顺序安排元素就行。每次判断当前的左右两个数谁更大，再把 $h$ 的新元素放到那边。

#include<bits/stdc++.h>
using namespace std;
int h[100005];
int v[100005];
int a[100005];
bool in[100005];
void mian(){
	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=3;i<=n;i++){//这里的 i 是目前填第几个数 
		if(a[l]>a[r]){
			while(in[h[nw]])nw++;
			a[++l]=h[nw];
			in[h[nw]]=1;
		}else{
			while(in[h[nw]])nw++;
			a[--r]=h[nw];
			in[h[nw]]=1;
		}
	}
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--)mian(); 
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N], nh[N], nhlen, p[N];
bool bk[N];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++)bk[i]=0;
        for(int i=1;i<n;i++) cin>>h[i], bk[h[i]]=1;
        nhlen=0;
        for(int i=1;i<=n;i++) if(!bk[i])nh[++nhlen]=i;

        int cnt_one=0;for(int i=1;i<n;i++)if(h[i]==1)cnt_one++;

        if(h[n-1]!=1 || nhlen>2 || (nhlen==2 && cnt_one!=2) )
        {
            cout<<"-1\n";
            continue;
        }
        
        if(nhlen==1) p[1]=1, p[n]=nh[1];
        else         p[1]=nh[1], p[n]=nh[2];

        for(int i=1, l=1, r=n;i<n;i++)
        {
            if(p[l]>p[r]) p[++l]=h[i];
            else          p[--r]=h[i];
        }
 
        for(int i=1;i<=n;i++)cout<<p[i]<<" ";
        cout<<"\n";
    }
    return 0;
}