1157C2. C2. Increasing Subsequence (hard version)

CF1157C2. Increasing Subsequence (hard version)

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

给你一个长度为 n 的序列，每次取出当前序列中最左或最右的数字，每次取出的数都要严格大于上一次取出的数，求最多取出多少数字。

输入格式

第一行一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$，两两不同）。

输出格式

第一行输出最多取出的数字个数 k

第二行按顺序输出 k 个字符‘L’或‘R’表示每次取左边或右边
多解输出任意一组

</p>

样例输入 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

提示

第一个样例已在题目描述中说明。