#P15. [CSP-S 2021] Palindromic deque

[CSP-S 2021] Palindromic deque

题目描述

给定正整数 nn 和整数序列 a1,a2,,a2na_1, a_2, \ldots, a_{2 n},在这 2n2 n 个数中,1,2,,n1, 2, \ldots, n 分别各出现恰好 22 次。现在进行 2n2 n 次操作,目标是创建一个长度同样为 2n2 n 的序列 b1,b2,,b2nb_1, b_2, \ldots, b_{2 n},初始时 bb 为空序列,每次可以进行以下两种操作之一:

  1. 将序列 aa 的开头元素加到 bb 的末尾,并从 aa 中移除。
  2. 将序列 aa 的末尾元素加到 bb 的末尾,并从 aa 中移除。

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

输入格式

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

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

第一行,包含一个正整数 nn
第二行,包含 2n2 n 个用空格隔开的整数 a1,a2,,a2na_1, a_2, \ldots, a_{2 n}

输出格式

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

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

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

字典序的比较规则如下:长度均为 2n2 n 的字符串 s12ns_{1 \sim 2 n}t12nt_{1 \sim 2 n} 字典序小,当且仅当存在下标 1k2n1 \le k \le 2 n 使得对于每个 1i<k1 \le i < ksi=tis_i = t_isk<tks_k < t_k

样例

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
LRRLLRRRRL
-1

提示

【样例解释 #1】

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

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

【样例 #2】

见选手目录下的 palin/palin2.in 和 palin/palin2.ans。

【数据范围】

n\sum n 表示所有 TT 组测试数据中 nn 的和。

对所有测试点保证 1T1001 \le T \le 1001n,n5×1051 \le n, \sum n \le 5 \times {10}^5

测试点编号 TT \le nn \le n\sum n \le 特殊性质
171 \sim 7 1010 5050
8108 \sim 10 100100 2020 10001000
111211 \sim 12 100100
131513 \sim 15 10001000 2500025000
161716 \sim 17 11 5×1055 \times {10}^5
182018 \sim 20 100100
212521 \sim 25

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