Increasing Subsequence (hard version)

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-07-19 19-30-49
  4**/
  5
  6#include <bits/stdc++.h>
  7
  8using namespace std;
  9
 10#ifdef DEBUG
 11string to_string(string s) {
 12	return '"' + s + '"';
 13}
 14
 15string to_string(const char* s) {
 16	return to_string((string) s);
 17}
 18
 19string to_string(bool b) {
 20return (b ? "true" : "false");
 21}
 22
 23template <typename A, typename B>
 24string to_string(pair<A, B> p) {
 25	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
 26}
 27
 28template <typename A>
 29string to_string(A v) {
 30	bool first = true;
 31	string res = "{";
 32	for (const auto &x : v) {
 33		if (!first) {
 34			res += ", ";
 35		}
 36		first = false;
 37		res += to_string(x);
 38	}
 39	res += "}";
 40	return res;
 41}
 42
 43void debug_out() { cerr << endl; }
 44
 45template <typename Head, typename... Tail>
 46void debug_out(Head H, Tail... T) {
 47	cerr << " " << to_string(H);
 48	debug_out(T...);
 49}
 50#endif
 51
 52#ifdef DEBUG
 53#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
 54#else
 55#define debug(...) 17
 56#endif
 57
 58#ifdef DEBUG
 59#define FAST_IO 17
 60#else
 61#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 62#define endl '\n'
 63#endif
 64
 65#define LL long long
 66#define ULL unsigned long long
 67#define rep(i, n) for(int i = 0; i < (n); ++i)
 68#define reep(i, n) for(int i = 0; i <= (n); ++i)
 69#define lop(i, a, n) for(int i = a; i < (n); ++i)
 70#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 71#define ALL(v) (v).begin(), (v).end()
 72#define PB push_back
 73#define VI vector<int>
 74#define PII pair<int,int>
 75#define FI first
 76#define SE second
 77#define SZ(x) ((int)(x).size())
 78
 79const double EPS = 1e-6;
 80const double PI = acos(-1.0);
 81const int INF = 0x3f3f3f3f;
 82const LL LINF = 0x7f7f7f7f7f7f7f7f;
 83const int MAXN = (int)1e6 + 10;
 84const int MOD = (int)1e9 + 7;
 85
 86int a[MAXN];
 87
 88int main(){
 89	FAST_IO;
 90
 91	int n;
 92	cin >> n;
 93	rep(i, n) cin >> a[i];
 94
 95	int last = -1, l = 0, r = n-1;
 96	string ans;
 97	while(l <= r){
 98		if(last >= a[l]){
 99			while(l <= r && last < a[r]){
100				ans.push_back('R');
101				last = a[r];
102				--r;
103			}
104			break;
105		}
106		if(last >= a[r]){
107			while(l <= r && last < a[l]){
108				ans.push_back('L');
109				last = a[l];
110				++l;
111			}
112			break;
113		}
114		if(a[l] < a[r]){
115			ans.push_back('L');
116			last = a[l];
117			++l;
118			continue;
119		}
120		if(a[r] < a[l]){
121			ans.push_back('R');
122			last = a[r];
123			--r;
124			continue;
125		}
126		int ll = 1;
127		while(ll < r-l+1 && a[l+ll] > a[l+ll-1]) ++ll;
128		int rr = 1;
129		while(rr < r-l+1 && a[r-rr] > a[r-rr+1]) ++rr;
130		if(ll >= rr) {
131			rep(i, ll) ans.push_back('L');
132		}else{
133			rep(i, rr) ans.push_back('R');
134		}
135		break;
136	}
137	cout << ans.size() << endl << ans << endl;
138
139	return 0;
140}