问题 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.