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

/*
（1）H 中不包含的数字最多 2 个，否则输出-1；
（2）H 中末尾的数字必是 1，否则输出-1；
（3）H 中出现多次的数字必是 1 且 最多2次，此时不包含的数字有 2 个，否则输出-1；
（4）H 中不包含的数字个数是 1 时，字典序最小的解在  P1<PN 的排列中，
1在首位，H不包含的那个数在排列末尾；
（5）H 中不包含的数字个数大于 1 时，字典序最小的解在  P1<PN 的排列中，
	排列首尾分别是这两个数，较小的数在首位；
*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		
		vector<int> h(n - 1);//vector初始大小
		for(int i = 0; i < n-1; i++)cin>>h[i];//输入h序列
		
		vector<bool> has(n + 1);//has[1]~has[n]
		for (int i : h) has[i] = 1;//标记 h 中出现的数字
		
		vector<int> not_has;//存h中未出现的数字
		for (int i = 1; i <= n; i++)//升序统计不在h中的数
			if (!has[i]) not_has.push_back(i);
		
		//统计 h 中 1 的个数
		int cnt_one = count(h.begin(), h.end(), 1);
		//h中只有1可能出现2次，其他数均最多出现1次
		if (not_has.size() > 2  //(1) 不包含的数>2个
			|| h.back()!= 1     //(2) h 末尾不是 1
			|| (not_has.size() == 2 && cnt_one!= 2))//（3）1出现2次，不包含2个数
		{
			cout << -1 << endl;//无解
			continue;//处理下一组数据
		}
		
		vector<int> p(n);
		if (not_has.size() == 1) {
			p[0] = 1;//排列首元素为 1
			//末尾元素为h中未包含的数字
			p[n - 1] = not_has[0];
		}
		
		if (not_has.size() > 1) {
			p[0] = not_has[0];//较小的数
			p[n - 1] = not_has[1];//较大的数
		}
		//确定首尾元素后，结合H即可确定P的其他元素
		int l = 0, r = n - 1;
		for (int i = 0; i < n - 1; i++)
		{//方法同：子任务2
			if (p[l] > p[r])
				p[++l] = h[i];
			else
				p[--r] = h[i];
		}
		for (int i = 0; i < n; i++) {
			if (i) cout << " ";
			cout << p[i];
		}//输出最优解
		cout << "\n";
	}
	return 0;
}