Codeforces Round #555 (Div. 3) C2. 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]

).

Input

The first line of the input contains one integer n

(1≤n≤2⋅105) — the number of elements in a

.

The second line of the input contains n

integers a1,a2,…,an (1≤ai≤2⋅105), where ai is the i-th element of a

.

Output

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 sj 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.

Examples

Input

Copy

5
1 2 4 3 2

Output

Copy

4
LRRR

Input

Copy

7
1 3 5 6 5 4 2

Output

Copy

6
LRLRRR

Input

Copy

3
2 2 2

Output

Copy

1
R

Input

Copy

4
1 2 4 3

Output

Copy

4
LLRR

Note

The first example is described in the problem statement.

#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define ll long long
#include<stack>
#include<set>
int a[220000];
char b[220000];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(b,0,sizeof(b));
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        int x=0,y=n+1,sum=0,t=0;
        while(x<y)
        {
            int x1,y1;
            x1=x+1;
            y1=y-1;
            if(x1==y1)
            {
                if(a[y1]>sum)
                {
                    y=y1;
                    x=x1;
                    b[t++]='R';
                }
                break;
            }
            if(a[x1]<=sum&&a[y1]<=sum)
                break;
            if(a[x1]>sum&&a[y1]>sum)
            {
                if(a[x1]>a[y1])
                {
                    sum=a[y1];
                    y=y1;
                    b[t++]='R';
                    continue;
                }
                else if(a[x1]==a[y1])
                {

                    int x2,y2,t1=1,t2=1;
                    for(int j=x1;j<=y1-1;j++)
                    {
                        if(a[j+1]>a[j]) t1++;
                        else break;
                    }
                    for(int j=y1;j>=x1+1;j--)
                    {
                        if(a[j-1]>a[j]) t2++;
                        else break;
                    }
                    if(t1>t2)
                    {
                        x=x1+t1-1;
                        y=y1-t1+1;
                        sum=a[x1+t1-1];
                        for(int i=1;i<=t1;i++) b[t++]='L';
                    }
                    else
                    {
                        y=y1-t2+1;
                        x=x1+t2-1;
                        sum=a[y1-t2+1];
                        for(int i=1;i<=t2;i++) b[t++]='R';
                    }
                    //printf("t1=%d t2=%d x=%d y=%d\n",t1,t2,x,y);
                    break;
                }
                else
                {
                    sum=a[x1];
                    x=x1;
                    b[t++]='L';
                    continue;
                }
            }
            else if(a[x1]>sum)
            {
                sum=a[x1];
                x=x1;
                b[t++]='L';
                continue;
            }
            else
            {
                sum=a[y1];
                y=y1;
                b[t++]='R';
                continue;
            }
        }
        printf("%d\n%s\n",t,b);
    }
}

 

全部评论

相关推荐

真tmd的恶心,1.面试开始先说我讲简历讲得不好,要怎样讲怎样讲,先讲背景,再讲技术,然后再讲提升多少多少,一顿说教。2.接着讲项目,我先把背景讲完,开始讲重点,面试官立即打断说讲一下重点,无语。3.接着聊到了项目的对比学习的正样本采样,说我正样本采样是错的,我解释了十几分钟,还是说我错的,我在上一家实习用这个方法能work,并经过市场的检验,并且是顶会论文的复现,再怎么不对也不可能是错的。4.面试官,说都没说面试结束就退出会议,把面试者晾在会议里面,丝毫不尊重面试者难受的点:1.一开始是讲得不好是欣然接受的,毕竟是学习。2.我按照面试官的要求,先讲背景,再讲技术。当我讲完背景再讲技术的时候(甚至已经开始蹦出了几个技术名词),凭什么打断我说讲重点,是不能听出人家重点开始了?这也能理解,每个人都有犯错,我也没放心上。3.我自己做过的项目,我了解得肯定比他多,他这样贬低我做过的项目,说我的工作是错误的,作为一个技术人员,我是完全不能接受的,因此我就和他解释,但无论怎么解释都说我错。凭什么,作为面试官自己不了解相关技术,别人用这个方式work,凭什么还认为这个方法是错的,不接受面试者的解释。4.这个无可厚非,作为面试官,不打招呼就退出会议,把面试者晾着,本身就是有问题。综上所述,我现在不觉得第一第二点也是我的问题,面试官有很大的问题,就是专门恶心人的,总结面试官说教,不尊重面试者,打击面试者,不接受好的面试者,技术一般的守旧固执分子。有这种人部门有这种人怎么发展啊。最后去查了一下,岗位关闭了。也有可能是招到人了来恶心人的,但是也很cs
牛客20646354...:招黑奴啊,算法工程师一天200?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务