B. 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,1,2,4,5,6]$ 是坏的，因为 $a_2 < a_3 < a_4 < a_5 < a_6$。
• $a = [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$ 中剩余元素的最左边或最右边的元素。设 $q_i$ 是在第 $i$ 轮被移除的元素。

选择在每一轮中移除哪个元素，使得最终得到的数组 $q$ 是好的。我们可以证明，在给定的约束条件下，总是有解的。

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

输入

每个测试包含多个测试用例。第一行是测试用例的数量 $t$ ($1 \leq t \leq 10000$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($5 \leq n \leq 100000$) — 数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$, $p_i$ 是两两不同的) — 排列的元素。

保证所有测试用例的 $n$ 的总和不超过 $200000$。

输出

对于每个测试用例，你必须输出一个长度为 $n$ 的字符串 $s$。对于每个 $1 \leq i \leq n$，在第 $i$ 轮中：

• $s_i = \mathtt{L}$ 表示你移除了 $p$ 的最左边元素
• $s_i = \mathtt{R}$ 表示你移除了 $p$ 的最右边元素

我们可以证明答案总是存在的。如果存在多个解，输出任意一个即可。

题解

基本思想是在奇数轮移除左右元素的较小者，在偶数轮移除左右元素的较大者。

更多细节请参考官方题解。