UOJ Logo LFYZ Online Judge

LFYZOJ

#403. [CSP-S 2021] 回文

统计

题目描述

给定正整数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,有b(i)=b(2n+1-i) 。

请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。

输入格式

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

输入的第一行,包含一个整数 T,表示测试数据的组数。对于每组测试数据:

第一行,包含一个正整数 n。 第二行,包含2n个用空格隔开的整数a1,a2...a2n。

输出格式

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

如果无法生成出回文数列,输出一行‐1,否则输出一行一个长度为2n的、由字符 L 或 R 构成的字符串(不含空格),其中 L 表示移除开头元素的操作 1,R 表示操作 2。

你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下:长度均为2n的字符串s1~2n比t1~2n字典序小,当且仅当存在下标n1≤k≤2n使得对于每个k 1≤i<k有si=ti且sk<tk。

输入输出样例

输入 #1

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,但比答案方案的字典序要大。

【数据范围】

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

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

|测试点编号|T≤|n≤|∑n≤|特殊性质|

|1∼7|10|10|50|无|

|8∼10|100|20|1000|无|

|11∼12|100|100|1000|无|

|13∼15|100|1000|25000|无|

|16∼17|1|5×10^5|5×10^5|无|

|18∼20|100|5×10^5|5×10^5|有|

|21-25|100|5×10^5|5×10^5|无|

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