#84. 回文

回文

题目描述

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

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

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

输入格式

从文件 palin.in 中读入数据。 每个测试点包含多组测试数据。 输入的第一行包含一个整数 TT,表示测试数据的组数。 每组测试数据的第一行包含一个正整数 nn,第二行包含 2n2n 个用空格隔开的整数 a1,a2,,a2na_1, a_2, \cdots , a_{2n}

输出格式

输出到文件 palin.out 中。 对每个测试数据输出一行答案。 如果无法生成出回文数列,输出一行 1‐1,否则输出一行一个长度为 2n2n 的、由字符 LLRR 构成的字符串(不含空格),其中 LL 表示移除开头元素的操作 11RR 表示操作 22。 你需要输出所有方案对应的字符串中字典序最小的一个。 字典序的比较规则如下:长度均为 2n2n 的字符串 s1..2ns_{1..2n} 比 $t_{1..2n} 字典序小,当且仅当存在下标 1k2n1 \leq k \leq 2n 使得 1i<k\forall 1 \leq 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\space 5\space 3\space 1\space 2\space 2\space 1\space 3\space 5\space 4$,可以看出这是一个回文数列。 另一种可能的操作方案是 LRRLLRRRRRLRRLLRRRRR,但比答案方案的字典序要大。

样例 2

见选手目录下的 palin2.inpalin2.ans

数据范围与提示

n\sum n 表示所有 TT 组测试数据中 nn 的和。 对所有测试点保证 $1 \leq T \leq 100, 1 \leq n, \sum n \leq 5 \times 10^5$。

测试点编号 TT nn n\sum n 特殊性质
171\sim 7 10\leq 10 50\leq 50
8108\sim 10 100\leq 100 20\leq 20 1000\leq 1000
111211\sim 12 100\leq 100
131513\sim 15 1000\leq 1000 25000\leq 25000
161716\sim 17 =1=1 5×105\leq 5 \times 10^5
182018\sim 20 100\leq 100
212521\sim 25

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