P7915 [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}$。请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【**输出格式**】中说明。

无

无

**【样例解释 #1】** 在第一组数据中，生成的的 $b$ 数列是 $[4, 5, 3, 1, 2, 2, 1, 3, 5, 4]$，可以看出这是一个回文数列。 另一种可能的操作方案是 `LRRLLRRRRR`，但比答案方案的字典序要大。 **【数据范围】** 令 $\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]$）。 **【hack 数据提供】** @[潜在了H2O下面](user/264490)。