$\texttt{Description}$

给定一个长度为 $2 \times n$ 的数列 $A$ 和一个空数列 $B$，每次可以从 $A$ 数列的最左边或最右边拿出一个数并放入 $B$ 数列的末尾，求字典序最小的方案。无方案则输出 -1。

$\texttt{Brute Force}$

这里给出 $28\texttt{pts}$ 的做法，也是最容易想的暴力深搜以及我在考场上骗分的思路。对于每一次操作，先从左往右扫描一遍，然后标记第一个没有被使用的数字，同时记录答案。然后再从右往左扫（为了保证字典序）。放一下这部分的代码。

$\texttt{Solution}$

首先可以想到，第一步只能从最左边或最右边选。此处讨论选最左边的方法。

如上图，若把开头的 $4$ 移走，为了保证回文，另外一个 $4$ 一定是最后一个移走的。因此，我们需要把红色方框内的数字全部移走才能保证合法。

现在考虑进行第二次操作。

显然，第二次操作只能拿走左边红框的第一个元素 $1$，或者右边红框最后的元素 $5$。到底应该取哪一个呢？

我们可以从倒数第二次操作来分析。在上图中，第二个 $4$ 是最后移走的，又因为每次只能移动最左边或最右边的元素，因此倒数第二个移走的一定是上图中第二个 $4$ 左边的 $2$ 或者右边的 $5$。

为了保证回文，第二次操作和倒数第二次操作移走的数必须相同。因此，这里只能移走 $5$（在代码中，这里要把两个 $5$ 同时移走，防止后面重复访问）。

结合刚才的具体例子，我们来归纳一下：

1. 找到序列中与第一个元素相同的元素，记录其位置 $i$。
2. 把 $A_1$ 到 $A_{i - 1}$ 放入一个数组，把 $A_{i +1}$ 到 $A_{2\times n}$ 放入另一个数组（这两个数组模拟上图中的红框）。
3. 此时可以移走的数字是左边红框的第一个元素和右边红框的最后一个元素。而与之对应的是左边红框的最后一个元素以及右边红框的第一个元素。若前两个元素中有一个与后两个元素中的一个相同，则删除这两个元素（如果没有相同的，就说明无法操作）。并且分别记录答案（左红框就记为 L，右红框就记为 R）。
4. 如果第三步无法操作，那么就找到序列中与最后一个元素相同的元素，记录位置 $j$。并重复类似于步骤 $2$ 和步骤 $3$ 的操作。

细节很多，其中红框可以通过双端队列（deque）实现。

$\texttt{AC Code}$：

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;

const int N = (5e5 + 10) * 2;
int T;
int a[N];
char ans[N], ans1[N];
deque<int> c, d;
bool flag, v;

void output(int cnt) {
    printf("%c", (v ? 'R' : 'L'));
    for (int i = 1; i <= cnt; i++) printf("%c", ans[i]);
    for (int i = cnt; i >= 1; i--) printf("%c", ans1[i]);
    printf("%c\n", 'L');
}

void check() {
    int cnt = 0;
    while (c.size() && d.size()) {
        int a, b, x, y;
        a = c.front(), b = c.back();
        x = d.front(), y = d.back();
        if (a == b && c.size() != 1) {
            ans[++cnt] = 'L', ans1[cnt] = 'L';
            c.pop_front(), c.pop_back();
            continue;
        }
        if (a == y) {
            ans[++cnt] = 'L', ans1[cnt] = 'R';
            c.pop_front(), d.pop_back();
            continue;
        }
        if (x == y && d.size() != 1) {
            ans[++cnt] = 'R', ans1[cnt] = 'R';
            d.pop_back(), d.pop_front();
            continue;
        }
        if (b == x) {
            ans[++cnt] = 'R', ans1[cnt] = 'L';
            c.pop_back(), d.pop_front();
            continue;
        }
        flag = true;
        return;
    }
  
    while (c.size()) {
        int a = c.front(), b = c.back();
        if (a == b) {
            ans[++cnt] = 'L', ans1[cnt] = 'L';
            c.pop_front();
            c.pop_back();
        }
        else {
            flag = true;
            return;
        }
    }
    while(d.size()) {
        int a = d.front(), b = d.back();
        if (a == b) {
            ans[++cnt] = 'R', ans1[cnt] = 'R';
            d.pop_front();
            d.pop_back();
        }
        else  {
            flag = true;
            return;
        }
    }
    output(cnt);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        flag = false, v = false;
        while (c.size()) c.pop_back();
        while (d.size()) d.pop_back();
        memset(ans, 0, sizeof(ans));
        int n, val;
        scanf("%d%d", &n, &a[1]);
        for (int i = 2; i <= 2 * n; ++i) {
            scanf("%d", a + i);
            if (a[i] == a[1]) val = i;
        }
  
        for (int i = 2; i < val; i++) c.push_back(a[i]);
        for (int i = 2 * n; i > val; i--) d.push_back(a[i]);

        check();
        if (flag == false) continue;
  
        flag = false, v = true;
        while (c.size()) c.pop_back();
        while (d.size()) d.pop_back();
        memset(ans, 0, sizeof(ans));

        for (int i = 2 * n - 1; i >= 1; i--) 
            if (a[i] == a[2 * n]) val = i;
        for (int i = 1; i < val; i++) c.push_back(a[i]);
        for (int i = 2 * n - 1; i > val; i--) d.push_back(a[i]);
        check();

        if (flag == true) printf("-1\n");
    }
    return 0;
}