P7915 [CSP-S 2021] Palindrome

Given a positive integer $n$ and an integer sequence $a_1, a_2, \ldots, a_{2 n}$, among these $2 n$ numbers, each of $1, 2, \ldots, n$ appears exactly $2$ times. Now perform $2 n$ operations, with the goal of creating a sequence $b_1, b_2, \ldots, b_{2 n}$ of the same length $2 n$. Initially, $b$ is an empty sequence. Each time, you may perform one of the following two operations: 1. Append the first element of sequence $a$ to the end of $b$, and remove it from $a$. 2. Append the last element of sequence $a$ to the end of $b$, and remove it from $a$. Our goal is to make $b$ a **palindromic sequence**, that is, it satisfies for all $1 \le i \le n$, $b_i = b_{2 n + 1 - i}$. Please determine whether this goal can be achieved. If it can, output the lexicographically smallest operation plan, as explained in **Output Format**.

Each test point contains multiple groups of testdata. The first line of input contains an integer $T$, the number of test cases. For each test case: The first line contains a positive integer $n$. The second line contains $2 n$ space-separated integers $a_1, a_2, \ldots, a_{2 n}$.

For each test case, output one line as the answer. If it is impossible to generate a palindromic sequence, output a line `-1`. Otherwise, output a string of length $2 n$ consisting of characters `L` or `R` (with no spaces), where `L` means removing the first element (operation 1), and `R` means operation 2. You need to output the lexicographically smallest string among all valid plans. The lexicographical order is defined as follows: for two strings $s_{1 \sim 2 n}$ and $t_{1 \sim 2 n}$ of length $2 n$, $s$ is lexicographically smaller than $t$ if and only if there exists an index $1 \le k \le 2 n$ such that for every $1 \le i < k$, $s_i = t_i$, and $s_k < t_k$.

**Sample Explanation #1** In the first group of data, the generated sequence $b$ is $[4, 5, 3, 1, 2, 2, 1, 3, 5, 4]$, and you can see that this is a palindromic sequence. Another possible operation plan is `LRRLLRRRRR`, but its lexicographical order is larger than the answer. **Constraints** Let $\sum n$ denote the sum of $n$ over all $T$ test cases. For all test points, it is guaranteed that $1 \le T \le 100$, $1 \le n, \sum n \le 5 \times {10}^5$. | Test Point ID | $T \le$ | $n \le$ | $\sum n \le$ | Special Property | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 7$ | $10$ | $10$ | $50$ | None | | $8 \sim 10$ | $100$ | $20$ | $1000$ | None | | $11 \sim 12$ | $100$ | $100$ | $1000$ | None | | $13 \sim 15$ | $100$ | $1000$ | $25000$ | None | | $16 \sim 17$ | $1$ | $5 \times {10}^5$ | $5 \times {10}^5$ | None | | $18 \sim 20$ | $100$ | $5 \times {10}^5$ | $5 \times {10}^5$ | Yes | | $21 \sim 25$ | $100$ | $5 \times {10}^5$ | $5 \times {10}^5$ | None | Special Property: If each time we delete two adjacent equal numbers in $a$, there exists a way to delete the entire sequence (for example, $a = [1, 2, 2, 1]$). **Hack testdata provided by** @[潜在了H2O下面](/user/264490)。 Translated by ChatGPT 5