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 翻译