题目描述
给定正整数 n 和整数序列 a1,a2,…,a2n,在这 2n 个数中,1,2,…,n 分别各出现恰好 2 次。现在进行 2n 次操作,目标是创建一个长度同样为 2n 的序列 b1,b2,…,b2n,初始时 b 为空序列,每次可以进行以下两种操作之一:
- 将序列 a 的开头元素加到 b 的末尾,并从 a 中移除。
- 将序列 a 的末尾元素加到 b 的末尾,并从 a 中移除。
我们的目的是让 b 成为一个回文数列,即令其满足对所有 1≤i≤n,有 bi=b2n+1−i。请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。
输入格式
每个测试点包含多组测试数据。
输入的第一行,包含一个整数 T,表示测试数据的组数。对于每组测试数据:
第一行,包含一个正整数 n。
第二行,包含 2n 个用空格隔开的整数 a1,a2,…,a2n。
输出格式
对每组测试数据输出一行答案。
如果无法生成出回文数列,输出一行 -1
,否则输出一行一个长度为 2n 的、由字符 L
或 R
构成的字符串(不含空格),其中 L
表示移除开头元素的操作 1,R
表示操作 2。
你需要输出所有方案对应的字符串中字典序最小的一个。
字典序的比较规则如下:长度均为 2n 的字符串 s1∼2n 比 t1∼2n 字典序小,当且仅当存在下标 1≤k≤2n 使得对于每个 1≤i<k 有 si=ti 且 sk<tk。
样例
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
LRRLLRRRRL
-1
提示
【样例解释 #1】
在第一组数据中,生成的的 b 数列是 [4,5,3,1,2,2,1,3,5,4],可以看出这是一个回文数列。
另一种可能的操作方案是 LRRLLRRRRR
,但比答案方案的字典序要大。
【样例 #2】
见选手目录下的 palin/palin2.in 和 palin/palin2.ans。
【数据范围】
令 ∑n 表示所有 T 组测试数据中 n 的和。
对所有测试点保证 1≤T≤100,1≤n,∑n≤5×105。
测试点编号 |
T≤ |
n≤ |
∑n≤ |
特殊性质 |
1∼7 |
10 |
50 |
无 |
8∼10 |
100 |
20 |
1000 |
11∼12 |
100 |
13∼15 |
1000 |
25000 |
16∼17 |
1 |
5×105 |
18∼20 |
100 |
有 |
21∼25 |
无 |
特殊性质:如果我们每次删除 a 中两个相邻且相等的数,存在一种方式将序列删空(例如 a=[1,2,2,1])。