Codeforces Round #756 (Div. 3) C. Polycarp Recovers the Permutation

一开始读错题意了，还以为是给定p求a，只能想到vector/双端队列模拟。

实际上，是给定会输出的数组，让我们求出原数组。

考虑题目给出的性质并根据题意中的模拟过程判断，不难看出原数组中的最大值一定会变成新数组的两端之一，这毫无疑问会是我们判断合法性的关键一步。

除了第一种不合法性，我们还要考虑，是否存在其他情况下的新数组，根本无法求得原数组？但观察原数组和新数组的关系可以发现，由于它们之间的关系本质上是"存在"与"不存在的关系"，而新数组的数字都可以对应到原数组中。而由于除了最大值一定被规定在两端之一放置，其他的任何数字都可以被某种方法考虑进行互换，从而最终得到"新数组"。

那么问题就转化成：已知一个可以被判定存在原数组的"新数组"，要求求出该数组的"原数组"。

考虑到原数组中左边的最小值会放到左边，右边的最小值会放到右边。不难联想到：是否可以直接扔进去"新数组"，就可以直接构造出"原数组"？

但是我们通过手动画图模拟会发现，在真正的执行过程中，新数组与原数组的对应关系"刚好相反"。换而言之，当一个数字在原数组是左边的最小值时，虽然会放到新数组的左边，但是也会造成原本在原数组相对较内部的数字反而更靠外部。

但是，最大值的位置永远是不变的。而最大值永远可以选择其他数字的位置。

实际上，如果模拟的次数足够多，会发现新数组中的"第一个数字"永远是个特例，也就是会无休止地往对应的位置放置。比如最大值在1上，那么最终数组实际上会倒转过来，在最大值位置正好相反的情况下也仍然成立。

#include
#include
using namespace std;
const int MAXN=3e5;
int a[MAXN];

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		if(a[1]!=n&&a[n]!=n){
			printf("-1\n");
			continue;
		}
		for(int i=n;i>=1;i--){
			printf("%d ",a[i]);
		}
		printf("\n");
	}
	
	return 0;
}