← 返回题目列表

Codeforces · 2128/B

B. 双端队列进程

中文机器翻译题面 查看原题

我们说大小为 $$$n$$$ 的数组 $$$a$$$ 是 坏 当且仅当存在 $$$1 \leq i \leq n - 4$$$ 且满足以下条件之一:

  • $$$a_i \lt a_{i+1} \lt a_{i+2} \lt a_{i+3} \lt a_{i+4}$$$
  • $$$a_i \gt a_{i+1} \gt a_{i+2} \gt a_{i+3} \gt a_{i+4}$$$

数组是 好 当且仅当它不是 坏。例如:

  • $$$a = [3, \color{红色}{1, 2, 4, 5, 6}]$$$ 是 坏 因为 $$$a_2 \lt a_3 \lt a_4 \lt a_5 \lt a_6$$$。
  • $$$a = [\color{红色}{7, 6, 5, 4, 1}, 2, 3]$$$ 是 坏 因为 $$$a_1 \gt a_2 \gt a_3 \gt a_4 \gt a_5$$$。
  • $$$a = [7, 6, 5, 1, 2, 3, 4]$$$ 是 好.

给你一个排列$$$^{\text{*}}$$$ $$$p_1, p_2, \ldots, p_n$$$。

你必须执行 $$$n$$$ 回合。每次,您必须删除 $$$p$$$ 中最左边或最右边的剩余元素。设 $$$q_i$$$ 为第 $$$i$$$ 轮移除的元素。

选择每次要删除的元素,以便生成的数组 $$$q$$$ 为 好。我们可以证明,在给定的约束下,它总是可能的。

$$$^{\text{*}}$$$长度$$$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$$$ 最右边的元素

我们可以证明答案总是存在的。如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

6
7
1 2 3 4 5 6 7
9
1 3 6 8 9 7 5 4 2
12
1 2 11 3 6 4 7 8 12 5 10 9
6
4 1 2 5 6 3
5
1 2 3 5 4
9
5 1 8 6 2 7 9 4 3

输出
复制

RRRLLLL
LLRRLLRRL
LLLLLLLLLLLL
LLLLLL
LLLLL
LLLLLLLLL

注意

在第一个测试用例中,序列 $$$\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}, \颜色{红色}{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}, \颜色{蓝色}{2}、\颜色{蓝色}{4}、\颜色{红色}{6}、\颜色{红色}{8}、\颜色{蓝色}{5}、\颜色{蓝色}{7}、\颜色{红色}{9}]$$$。