Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C2. Возрастающая подпоследовательность (усложнённая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие в задачах C1 и C2 состоит в том, что все входные значения в C1 различны (в задаче C2 это условие может не выполняться).

Задана последовательность $$$a$$$, состоящая из $$$n$$$ целых чисел.

Вы совершаете последовательность ходов. В течение каждого хода вы должны взять либо самый левый, либо самый правый элемент последовательности, выписать его и удалить из последовательности. Ваша задача — выписать строго возрастающую последовательность, и среди всех таких последовательностей вы должны выбрать самую длинную (длина последовательности равна количеству элементов в ней).

Например, для последовательности $$$[1, 2, 4, 3, 2]$$$ ответ равен $$$4$$$ (вы берете $$$1$$$, последовательность превращается в $$$[2, 4, 3, 2]$$$, затем вы берете правый элемент $$$2$$$ и последовательность превращается в $$$[2, 4, 3]$$$, затем вы берете $$$3$$$ и последовательность превращается в $$$[2, 4]$$$ и, наконец, вы берете $$$4$$$ и последовательность превращается в $$$[2]$$$, получившаяся возрастающая последовательность равна $$$[1, 2, 3, 4]$$$).

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

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в $$$a$$$.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ равно $$$i$$$-му элементу $$$a$$$.

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

В первой строке выведите $$$k$$$ — максимальное количество элементов в строго возрастающей последовательности, которое вы можете получить.

Во второй строке выведите строку $$$s$$$ длины $$$k$$$, где $$$j$$$-й символ строки $$$s_j$$$ должен быть равен 'L', если вы берете самый левый элемент в течение $$$j$$$-го хода, и 'R' в ином случае. Если существует несколько возможных ответов, вы можете вывести любой из них.

Примеры
Входные данные
5
1 2 4 3 2
Выходные данные
4
LRRR
Входные данные
7
1 3 5 6 5 4 2
Выходные данные
6
LRLRRR
Входные данные
3
2 2 2
Выходные данные
1
R
Входные данные
4
1 2 4 3
Выходные данные
4
LLRR
Примечание

Первый тестовый пример разобран в условии задачи.