[CSP-S 2021] 回文

题目描述

给定正整数 $n$ 和整数序列 $a_1,a_2,\ldots,a_{2n}$。在这 $2n$ 个数中，$1,2,\ldots,n$ 分别各出现恰好 $2$ 次。

现在进行 $2n$ 次操作，目标是创建一个长度同样为 $2n$ 的序列 $b$。初始时 $b$ 为空，每次可以进行以下两种操作之一：

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

目标是让 $b$ 成为回文序列，即对所有 $1\le i\le n$，有 $b_i=b_{2n+1-i}$。

若可以实现，请输出字典序最小的操作方案；否则输出 -1。其中 L 表示取开头，R 表示取末尾。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：第一行一个正整数 $n$；第二行 $2n$ 个用空格分隔的整数 $a_1,a_2,\ldots,a_{2n}$。

输出格式

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

若无法生成回文序列，输出 -1；否则输出一个长度为 $2n$、仅由字符 L 和 R 构成的字符串，表示所有方案中字典序最小的一个。

长度相同的字符串按通常字典序比较，且 L 小于 R。

样例 #1

输入 #1

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

输出 #1

LRRLLRRRRL
-1

数据范围与提示

样例 #1 的第一组数据中，一种生成的回文序列为 $[4,5,3,1,2,2,1,3,5,4]$。另一种可行方案是 LRRLLRRRRR，但其字典序大于输出方案。

数据范围与提示

令 $\sum n$ 表示所有测试数据中 $n$ 的和。对于所有测试点，$1\le T\le 100$，$1\le n,\sum n\le 5\times 10^5$。

测试点编号	$T\le$	$n\le$	$\sum n\le$	特殊性质
$1\sim7$	$10$		$50$	无
$8\sim10$	$100$	$20$	$1000$
$11\sim12$		$100$
$13\sim15$		$1000$	$25000$
$16\sim17$	$1$	$5\times10^5$
$18\sim20$	$100$			特殊
$21\sim25$				无

特殊性质：如果每次删除序列 $a$ 中两个相邻且相等的数，存在一种方式将序列删空。

附件下载

palin.zip