CF2128B.Deque Process

我们称一个长度为 $n$ 的数组 $a$ 是坏的，当且仅当存在 $1 \leq i \leq n-4$，使得以下两个条件之一成立：

• $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}$

如果数组不是坏的，则称其为好的。例如：

• $a = [3, \color{red}{1, 2, 4, 5, 6}]$ 是坏的，因为 $a_2 < a_3 < a_4 < a_5 < a_6$。
• $a = [\color{red}{7, 6, 5, 4, 1}, 2, 3]$ 是坏的，因为 $a_1 > a_2 > a_3 > a_4 > a_5$。
• $a = [7, 6, 5, 1, 2, 3, 4]$ 是好的。

现在给定一个排列 $^*$ $p_1, p_2, \ldots, p_n$。

你需要进行 $n$ 次操作。每次操作，你可以移除 $p$ 的最左端或最右端的一个元素。设第 $i$ 次操作移除的元素为 $q_i$。

请你选择每一步移除哪一端的元素，使得最终得到的数组 $q$ 是好的。可以证明，在给定的约束下，总是存在解。

$^*$ 一个长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但数组中有 $4$）。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$5 \leq n \leq 100\,000$），表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$，$p_i$ 互不相同），表示排列的元素。

保证所有测试用例中 $n$ 的总和不超过 $200\,000$。

对于每个测试用例，输出一个长度为 $n$ 的字符串 $s$。对于每个 $1 \leq i \leq n$，第 $i$ 次操作：

• $s_i = \texttt{L}$ 表示移除 $p$ 最左端的元素
• $s_i = \texttt{R}$ 表示移除 $p$ 最右端的元素

可以证明总是存在解。如果有多种方案，输出任意一种均可。

在第一个测试用例中，操作序列 $\color{blue}{\texttt{RRR}}\color{red}{\texttt{LLLL}}$ 得到 $q = [\color{blue}{7}, \color{blue}{6}, \color{blue}{5}, \color{red}{1}, \color{red}{2}, \color{red}{3}, \color{red}{4}]$。

在第二个测试用例中，操作序列 $\color{red}{\texttt{LL}}\color{blue}{\texttt{RR}}\color{red}{\texttt{LL}}\color{blue}{\texttt{RR}}\color{red}{\texttt{L}}$ 得到 $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}]$。

由 ChatGPT 4.1 翻译