B. Процесс на Деке
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив $$$a$$$ размера $$$n$$$ плохим, если и только если существует $$$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{red}{1, 2, 4, 5, 6}]$$$ является плохим, потому что $$$a_2 \lt a_3 \lt a_4 \lt a_5 \lt a_6$$$.
  • $$$a = [\color{red}{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$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите строку $$$s$$$ длины $$$n$$$. Для каждого $$$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}, \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}]$$$.