回文（palin）

回文（palin）

题号：NC229947
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定正整数 $n$ 和整数序列 $a_1,a_2, . . . ,a_{2n}$ ，在这 $2n$ 个数中， $1,2, . . . ,n$ 分别各出现恰好 $2$ 次。现在进行 $2n$ 次操作，目标是创建一个长度同样为 $2n$ 的序列 $b_1,b_2, . . . ,b_{2n}$ ，初始时 $b$ 为空序列，每次可以进行以下两种操作之一：

1.将序列 $a$ 的开头元素加到b的末尾，并从 $a$ 中移除

2.将序列 $a$ 的末尾元素加到b的末尾，并从 $a$ 中移除

我们的目的是让 $b$ 成为一个回文数列，即令其满足对所有 $1≤i≤n$ ，有 $b_i=b_{2n+1−i}$ 。请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。

输入描述:

每个测试点包含多组测试数据。

输入的第一行包含一个整数 $T$ ，表示测试数据的组数。

每组测试数据的第一行包含一个正整数 $n$ ，第二行包含 $2n$ 个用空格隔开的整数 $a_1, a_2, . . . , a_{2n}$ _。

输出描述:

对每个测试数据输出一行答案。

如果无法生成出回文数列，输出一行 $‐1$ ，否则输出一行一个长度为 $2n$ 的、由字符 $L$ 或 $R$ 构成的字符串（不含空格），其中 $L$ 表示移除开头元素的操作 $1，R$ 表示操作 $2$ 。你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下：长度均为 $2n$ 的字符串 $s_{1..2n}$ 比 $t_{1..2n}$ 字典序小，当且仅当存在下标 $1≤k≤2n$ 使得 $∀1≤i < k$ 有 $s_i=t_i$ 且 $s_k<t_k$ 。

示例1

输入

复制

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3

输出

复制

LRRLLRRRRL
-1

说明

在第一组数据中，生成的的b数列是 4 5 3 1 2 2 1 3 5 4，可以看出这是一个回文数列。

另一种可能的操作方案是LRRLLRRRRR，但比答案方案的字典序要大。

备注:

令 $∑n$ 表示所有T组测试数据中n的和。

对所有测试点保证 $1≤T≤100,1≤n, ∑n ≤5×10^5$ 。

特殊性质：如果我们每次删除a中两个相邻且相等的数，存在一种方式将序列删空（例如 $a= [1,2,2,1]$ ）。