CF1157C2.Increasing Subsequence (hard version)

The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence $a$ consisting of $n$ integers.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence $[1, 2, 4, 3, 2]$ the answer is $4$ (you take $1$ and the sequence becomes $[2, 4, 3, 2]$, then you take the rightmost element $2$ and the sequence becomes $[2, 4, 3]$, then you take $3$ and the sequence becomes $[2, 4]$ and then you take $4$ and the sequence becomes $[2]$, the obtained increasing sequence is $[1, 2, 3, 4]$).

问题 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]$）。

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the $i$-th element of $a$.

输入的第一行包含一个整数 $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$ 个元素。

In the first line of the output print $k$ — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string $s$ of length $k$, where the $j$-th character of this string $s_j$ should be 'L' if you take the leftmost element during the $j$-th move and 'R' otherwise. If there are multiple answers, you can print any.

在输出的第一行打印 $k$ —— 你能得到的严格递增序列的最大元素个数。

在第二行打印一个长度为 $k$ 的字符串 $s$，其中该字符串的第 $j$ 个字符 $s_j$ 在第 $j$ 次操作中取最左端元素时应为 'L'，否则为 'R'。若存在多个答案，输出任意一个即可。

The first example is described in the problem statement.

第一个示例在题目描述中已给出。