构造、贪心

如果第一次操作取出了最左边的数 $a_1$，那么最后一次操作必须取出序列中的另一个 $a_1$ 完成回文。

于是通过第一次操作可以确定最后一次操作，也就是说第一次操作和与之对应的最后一次操作将序列 $a$ 分割为两个双端队列，使用 $L$ 表示左边的双端队列，$R$ 表示右边的双端队列。

接下来的第二次操作和与之对应的倒数第二次操作，第二次操作将会在 $L$ 的左端或 $R$ 的右端取出一个数，倒数第二次操作将会在 $L$ 的右端或 $R$ 的左端取出一个数，由于回文的性质这两个数必须相等。

由于要求字典序最小的解，如果能操作 $L$ 的左端那么必然优先操作 $L$ 的左端。

在第一次操作确定时，存在 $L$ 的左端和 $R$ 的右端都可操作，而先操作 $R$ 的右端有解而先操作 $L$ 的左端无解的情况吗？不存在，因为序列中每个数恰好出现两次，两个操作互不影响。第一次操作将序列“分割”成两个双端队列，如果第一次操作取出 $a_1$ 不行再尝试第一次操作取出 $a_{2n}$，两种方案都不可行则问题无解。

注意特判 $L$ 或 $R$ 仅剩一个元素的情况，这个元素不能和自己配对。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
ifstream fin("palin.in");
ofstream fout("palin.out");
int n,a[1'000'005];
string run(list<int> l,list<int> r){
    string retl,retr;
    for(int i=1;i<=n-1;i++){
        int ll=0,lr=0,rl=0,rr=0;
        if(!l.empty()) ll=l.front(),lr=l.back();
        if(!r.empty()) rl=r.front(),rr=r.back();
        if(ll&&l.size()!=1u&&ll==lr){//特判l只剩一个元素的情况
            retl+='L',retr+='L';
            l.pop_front();
            l.pop_back();
        }
        else if(ll&&ll==rl){
            retl+='L',retr+='R';
            l.pop_front();
            r.pop_front();
        }
        else if(rr&&rr==lr){
            retl+='R',retr+='L';
            r.pop_back();
            l.pop_back();
        }
        else if(rr&&r.size()!=1u&&rr==rl){//特判r只剩一个元素的情况
            retl+='R',retr+='R';
            r.pop_back();
            r.pop_front();
        }
        else return "-1";
    }
    reverse(retr.begin(),retr.end());
    return retl+retr;
}
void solution(){
    fin>>n;
    for(int i=1;i<=n*2;i++) fin>>a[i];
    int pre=find(a+2,a+n*2+1,a[1])-a,suf=find(a+1,a+n*2,a[n*2])-a;
    string ans=run(list<int>(a+2,a+pre),list<int>(a+pre+1,a+n*2+1));
    if(ans!="-1") return fout<<'L'<<ans<<'L'<<'\n',void();
    ans=run(list<int>(a+1,a+suf),list<int>(a+suf+1,a+n*2));
    if(ans!="-1") return fout<<'R'<<ans<<'L'<<'\n',void();
    fout<<"-1"<<'\n';
}
int T;
int main(){
    fin>>T;
    while(T--) solution();
    return 0;
}