回文

吐槽：这题的字典序最小是答案字符串的字典序最小。

题目大意

给定一个长为 \(2n\) 的序列，由数字 \(1\rightarrow n\) 组成，且每个数字有两个。

每次操作要么选择左端点要么选择右端点，选择后将该数字从序列里删除并加入另一个序列的末尾，要求最后得到的序列是一个回文串。

输出一个长为 \(2n\) 的字符串，为每一次的选择，选左端点为 \(L\) ，选右端点为 \(R\) 。

若有多种方案，输出字典序最小的那一个。

分析

手玩一下样例，可以发现以下性质：

• 每当我们取一个数，我们必定能在序列中间的某个位置找到与这个数相同的数。

• 由于是回文串，我们可以将其分为两半取，先考虑前一半，发现前一半越先取后一半就要越后取。

于是，我们能够推出一个比较重要的性质。

假设我们取了一个数，在中间某个位置找到了它，又取了另外一个数，同样在中间某个位置找到了和它相同的那个数。这两个对应位置如果不相连，必然可以相信，它们中间的数会在未来某个位置被我们取到，根据上述性质 \(2\) ，我们要在两个后取的数的包裹下取一个先取的数，显然是不合题意的。

所以，我们可以把序列分为两部分，一部分是端点，一部分是已经选的数的映射区间，要保证，该区间必须连续，所以每次选的数必须要在这个区间的两边扩展，也就是说只能选这个区间的两边对应的数。简单的，如果无法进行扩展，说明我们的匹配失败了。

我们可以维护四个指针，然后能选左就选左，否则考虑选右，由于最开始我们没有区间，于是我们进行两次这个操作，第一次最开始选择左端点，第二次最开始选择右端点，若第一次已经成功那么就是最优解，否则进行第二次。
若两次都失败，则无解。

CODE

#include 
using namespace std;
const int N=5e5+10;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w*=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;	
}
int T,n;
int R[N],a[2*N];
int num[N];
char ans[2*N],temp[2*N];
bool flag;
inline void Solve(int x,int y,int A,int B) //记录目前的位置 
{
	int cnt=1;
	while(cnt