记录编号	596195	评测结果	AAAAAAAAAA
题目名称	[USACO24 Open Bronze]Farmer John’s Favorite Permutation	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.902 s
提交时间	2024-10-23 11:48:19	内存使用	3.98 MiB

#include <bits/stdc++.h>
using namespace std;
int T,n,a[500005],vis[500005],i1,i2,lose,ans[500005],hd,tl;
int main() {
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout); 
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) {
        i1=i2=lose=0;
        cin>>n;
        for(int i=1;i<=n;++i) {
            ans[i]=0;
            if(i<n)cin>>a[i];
            vis[i]=0;
        }
        for(int i=1;i<n-1;++i) {
            if(vis[a[i]]) {
                lose=1;
                break;
            }
            vis[a[i]]=1;
        }
        if(a[n-1]!=1) lose=1; 
        if(lose) {
            cout<<-1<<endl;
            continue;
        }
        for(int i=1;i<=n;++i) {
            if(vis[i]) continue;
            if(!i1) i1=i;
            else i2=i;
        }
        hd=1,tl=n;
        ans[1]=i1,ans[n]=i2;
        for(int i=1;i<n-1;++i) {
            if(ans[tl]>ans[hd]) ans[--tl]=a[i];
            else ans[++hd]=a[i];
        }
        for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}