问题 C1 和 C2 之间的唯一区别是问题 C1 输入中的所有值都是不同的(对于问题 C2,此条件可能为假)。
给定一个由 $$$n$$$ 整数组成的序列 $$$a$$$。所有这些整数都是不同的,从 $$$1$$$ 到 $$$n$$$ 的每个值在序列中只出现一次。
您正在执行一系列动作。在每次移动过程中,您必须取出序列中最左边的元素或序列中最右边的元素,将其写下来并将其从序列中删除。你的任务是写出一个严格递增的序列,并且在所有这样的序列中你应该取最长的(序列的长度是其中元素的数量)。
例如,对于序列$$$[2, 1, 5, 4, 3]$$$,答案是$$$4$$$(你取$$$2$$$,序列变成$$$[1, 5, 4, 3]$$$,然后你取最右边的元素$$$3$$$,序列变成$$$[1, 5, 4]$$$,然后你取$$$4$$$,序列变为$$$[1, 5]$$$,然后取$$$5$$$,序列变为$$$[1]$$$,得到的递增序列为$$$[2, 3, 4, 5]$$$)。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。所有这些整数都是成对不同的。
输出
在输出的第一行打印 $$$k$$$ — 您可以获得的严格递增序列中的最大元素数。
在第二行中打印一个长度为 $$$k$$$ 的字符串 $$$s$$$,其中如果在第 $$$j$$$ 次移动过程中获取最左边的元素,则该字符串 $$$s_j$$$ 的第 $$$j$$$ 个字符应为“L”,否则为“R”。如果有多个答案,您可以打印任何一个。
示例
输入 #1
5 2 1 5 4 3
输出 #1
4 LRRR
输入 #2
7 1 3 5 6 7 4 2
输出 #2
7 LRLRLLL
输入 #3
3 1 2 3
输出 #3
3 LLL
输入#4
4 1 2 4 3
输出#4
4 LLRL
注意
第一个示例在问题陈述中进行了描述。