13 · [CSP-S 2021] 回文

题目描述

给定正整数 $n$ 和整数序列 $a_1, a_2, \ldots, a_{2 n}$，在这 $2 n$ 个数中，$1, 2, \ldots, n$ 分别各出现恰好 $2$ 次。现在进行 $2 n$ 次操作，目标是创建一个长度同样为 $2 n$ 的序列 $b_1, b_2, \ldots, b_{2 n}$，初始时 $b$ 为空序列，每次可以进行以下两种操作之一： 1. 将序列 $a$ 的开头元素加到 $b$ 的末尾，并从 $a$ 中移除。 2. 将序列 $a$ 的末尾元素加到 $b$ 的末尾，并从 $a$ 中移除。 我们的目的是让 $b$ 成为一个回文数列，即令其满足对所有 $1 \le i \le n$，有 $b_i = b_{2 n + 1 - i}$。请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。

每个测试点包含多组测试数据。 输入的第一行，包含一个整数 $T$，表示测试数据的组数。对于每组测试数据： 第一行，包含一个正整数 $n$。 第二行，包含 $2 n$ 个用空格隔开的整数 $a_1, a_2, \ldots, a_{2 n}$。 【数据范围】 令 $\sum n$ 表示所有 $T$ 组测试数据中 $n$ 的和。 对所有测试点保证 $1 \le T \le 100$，$1 \le n, \sum n \le 5 \times {10}^5$。 测试点编号$T \le$$n \le$$\sum n \le$特殊性质$1 \sim 7$$10$$10$$50$无$8 \sim 10$$100$$20$$1000$无$11 \sim 12$$100$$100$$1000$无$13 \sim 15$$100$$1000$$25000$无$16 \sim 17$$1$$5 \times {10}^5$$5 \times {10}^5$无$18 \sim 20$$100$$5 \times {10}^5$$5 \times {10}^5$有$21 \sim 25$$100$$5 \times {10}^5$$5 \times {10}^5$无 特殊性质：如果我们每次删除 $a$ 中两个相邻且相等的数，存在一种方式将序列删空（例如 $a = [1, 2, 2, 1]$）。

测试点编号	$T \le$	$n \le$	$\sum n \le$	特殊性质
$1 \sim 7$	$10$	$10$	$50$	无
$8 \sim 10$	$100$	$20$	$1000$	无
$11 \sim 12$	$100$	$100$	$1000$	无
$13 \sim 15$	$100$	$1000$	$25000$	无
$16 \sim 17$	$1$	$5 \times {10}^5$	$5 \times {10}^5$	无
$18 \sim 20$	$100$	$5 \times {10}^5$	$5 \times {10}^5$	有
$21 \sim 25$	$100$	$5 \times {10}^5$	$5 \times {10}^5$	无

对每组测试数据输出一行答案。 如果无法生成出回文数列，输出一行 -1，否则输出一行一个长度为 $2 n$ 的、由字符 L 或 R 构成的字符串（不含空格），其中 L 表示移除开头元素的操作 1，R 表示操作 2。 你需要输出所有方案对应的字符串中字典序最小的一个。 字典序的比较规则如下：长度均为 $2 n$ 的字符串 $s_{1 \sim 2 n}$ 比 $t_{1 \sim 2 n}$ 字典序小，当且仅当存在下标 $1 \le k \le 2 n$ 使得对于每个 $1 \le 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

输出 #1

LRRLLRRRRL
-1