← 返回题目列表

Codeforces · 1157/C2

C2. 增加子序列(硬版本)

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

问题 C1 和 C2 之间的唯一区别是问题 C1 输入中的所有值都是不同的(对于问题 C2,此条件可能为假)。

给定一个由 $$$n$$$ 整数组成的序列 $$$a$$$。

您正在执行一系列动作。在每次移动过程中,您必须取出序列中最左边的元素或序列中最右边的元素,将其写下来并将其从序列中删除。你的任务是写出一个严格递增的序列,并且在所有这样的序列中你应该取最长的(序列的长度是其中元素的数量)。

例如,对于序列$$$[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$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

输出

在输出的第一行打印 $$$k$$$ — 您可以获得的严格递增序列中的最大元素数。

在第二行中打印一个长度为 $$$k$$$ 的字符串 $$$s$$$,其中如果在第 $$$j$$$ 次移动期间获取最左边的元素,则该字符串 $$$s_j$$$ 的第 $$$j$$$ 个字符应为“L”,否则为“R”。如果有多个答案,您可以打印任何一个。

示例

输入 #1

5
1 2 4 3 2

输出 #1

4
LRRR

输入 #2

7
1 3 5 6 5 4 2

输出 #2

6
LRLRRR

输入 #3

3
2 2 2

输出 #3

1
R

输入#4

4
1 2 4 3

输出#4

4
LLRR

注意

The first example is described in the problem statement.