B. Deque Process
constructive algorithms; greedy; sortings; two pointers
We say that an array \(a\) of size \(n\) is bad if and only if there exists \(1 \leq i \leq n - 4\) such that one of the following conditions holds: \(a_i < a_{i+1} < a_{i+2} < a_{i+3} < a_{i+4}\) \(a_i > a_{i+1} > a_{i+2} > a_{i+3} > a_{i+4}\) An array is good if and only if it's not bad. For example: \(a = [3, \color{red}{1, 2, 4, 5, 6}]\) is bad because \(a_2 < a_3 < a_4 < a_5 < a_6\). \(a = [\color{red}{7, 6, 5, 4, 1}, 2, 3]\) is bad because \(a_1 > a_2 > a_3 > a_4 > a_5\). \(a = [7, 6, 5, 1, 2, 3, 4]\) is good. You're given a permutation\(^{\text{∗}}\) \(p_1, p_2, \ldots, p_n\).You must perform \(n\) turns. At each turn, you must remove either the leftmost or the rightmost remaining element in \(p\). Let \(q_i\) be the element removed at the \(i\)-th turn.Choose which element to remove at each turn so that the resulting array \(q\) is good. We can show that under the given constraints, it's always possible.\(^{\text{∗}}\)A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array).
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10\,000\)). The description of the test cases follows. The first line of each test case contains a single integer \(n\) (\(5 \leq n \leq 100\,000\)) — the length of the array.The second line of each test case contains \(n\) integers \(p_1, p_2, \ldots, p_n\) (\(1 \leq p_i \leq n\), \(p_i\) are pairwise distinct) — elements of the permutation.It is guaranteed that the sum of \(n\) over all test cases doesn't exceed \(200\,000\).
For each test case, you must output a string \(s\) of length \(n\). For every \(1 \leq i \leq n\), at the \(i\)-th turn: \(s_i = \texttt{L}\) means that you removed the leftmost element of \(p\) \(s_i = \texttt{R}\) means that you removed the rightmost element of \(p\) We can show that an answer always exists. If there are multiple solutions, print any of them.
In the first test case, the sequence \(\color{blue}{\texttt{RRR}}\color{red}{\texttt{LLLL}}\) results in \(q = [\color{blue}{7}, \color{blue}{6}, \color{blue}{5}, \color{red}{1}, \color{red}{2}, \color{red}{3}, \color{red}{4}]\).In the second test case, the sequence \(\color{red}{\texttt{LL}}\color{blue}{\texttt{RR}}\color{red}{\texttt{LL}}\color{blue}{\texttt{RR}}\color{red}{\texttt{L}}\) results in \(q = [\color{red}{1}, \color{red}{3}, \color{blue}{2}, \color{blue}{4}, \color{red}{6}, \color{red}{8}, \color{blue}{5}, \color{blue}{7}, \color{red}{9}]\).