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. All these integers are distinct, each value from $1$ to $n$ appears in the sequence exactly once.

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 $[2, 1, 5, 4, 3]$ the answer is $4$ (you take $2$ and the sequence becomes $[1, 5, 4, 3]$, then you take the rightmost element $3$ and the sequence becomes $[1, 5, 4]$, then you take $4$ and the sequence becomes $[1, 5]$ and then you take $5$ and the sequence becomes $[1]$, the obtained increasing sequence is $[2, 3, 4, 5]$).


-----Input-----

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 n$), where $a_i$ is the $i$-th element of $a$. All these integers are pairwise distinct.


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


-----Examples-----
Input
5
2 1 5 4 3

Output
4
LRRR

Input
7
1 3 5 6 7 4 2

Output
7
LRLRLLL

Input
3
1 2 3

Output
3
LLL

Input
4
1 2 4 3

Output
4
LLRL



-----Note-----

The first example is described in the problem statement.

Difficulty: introductory

Starter code:

Solutions:
x=int(input())
a=list(map(int,input().strip().split()))
y=[]
c=0
f1=1
f2=1
l=0
r=x-1
op=[]
while(f1 or f2):
    if(l>r):
        break
    if(a[l]<c):
        f1=0
    if(a[r]<c):
        f2=0
    if(f1 and f2):
        if(a[l]<=a[r]):
            c=a[l]
            l=l+1
            op.append('L')
        else:
            c=a[r]
            r=r-1
            op.append('R')
    elif(f1):
        c=a[l]
        l=l+1
        op.append('L')
    elif(f2):
        c=a[r]
        r=r-1
        op.append('R')
print(len(op))
print("".join(op))


n = int(input())
a = list(map(int,input().split()))
t = 0
c = 0
l = 0
b = ''
r = n-1
while l<=r:
    m1 = min(a[l],a[r])
    m2 = max(a[l],a[r])
    if m1>t:
        t = m1
        if m1==a[r]:
            r-=1
            b+='R'
        elif m1==a[l]:
            l+=1
            b+='L'
        c+=1
    elif m2>t:
        t = m2
        if m2==a[r]:
            r-=1
            b+='R'
        elif m2==a[l]:
            l+=1
            b+='L'
        c+=1
    else:
        break

print(c)
print(b)


# AC
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = sys.stdin.readline().split()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_int(self):
        return int(next(self))

    def solve(self):
        n = self.next_int()
        x = [self.next_int() for _ in range(0, n)]
        d = 0
        l = 0
        r = n - 1
        rs = []
        while l <= r:
            if x[l] < d and x[r] < d:
                break
            if x[l] < d:
                rs.append('R')
                d = x[r]
                r -= 1
            elif x[r] < d:
                rs.append('L')
                d = x[l]
                l += 1
            elif x[r] < x[l]:
                rs.append('R')
                d = x[r]
                r -= 1
            else:
                rs.append('L')
                d = x[l]
                l += 1
        print(len(rs))
        print(''.join(rs))


def __starting_point():
    Main().solve()

__starting_point()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    i = 0
    j = n - 1
    k = 0
    mi = 0
    ans = ""
    while True:
        if a[i] < a[j]:
            if mi < a[i]:
                mi = a[i]
                i += 1
                ans += "L"
            elif mi < a[j]:
                mi = a[j]
                j -= 1
                ans += "R"
            else:
                break
        else:
            if mi < a[j]:
                mi = a[j]
                j -= 1
                ans += "R"
            elif mi < a[i]:
                mi = a[i]
                i += 1
                ans += "L"
            else:
                break
    print(len(ans))
    print(ans)
    return 0

main()

from collections import deque
n = int(input())
A = list(map(int, input().split()))
A = deque(A)
ans = ''
last = 0
while len(A) and (A[0] > last or A[-1] > last):
    if A[0] > last and A[-1] > last:
        if A[0] < A[-1]:
            last = A[0]
            A.popleft()
            ans += 'L'
        else:
            last = A[-1]
            A.pop()
            ans += 'R'
    else:
        if A[0] > last:
            last = A[0]
            A.popleft()
            ans += 'L'
        else:
            last = A[-1]
            A.pop()
            ans += 'R'
print(len(ans))
print(ans)


import sys

input = sys.stdin.readline

n = int(input())

a = list(map(int, input().split()))

last = 0
left = 0
right = n-1
ans = 0
output = []

while left <= right:
  if a[left] > last:
    if a[right] > last:
      if a[left] < a[right]:
        last = a[left]
        output.append('L')
        left += 1
      else:
        last = a[right]
        output.append('R')
        right -= 1
    else:
      last = a[left]
      output.append('L')
      left += 1
    ans += 1
  elif a[right] > last:
    last = a[right]
    output.append('R')
    right -= 1
    ans += 1
  else:
    break

print(ans)
print(''.join(output))



from collections import *

n = int(input())

M = deque(list(map(int, input().split())))

ans = []
last = None
while len(M) > 0:
    if ans == []:
        if M[-1] <= M[0]:
            ans += ['R']
            last = M[-1]
            M.pop()
        else:
            ans += ['L']
            last = M[0]
            M.popleft()
    else:
        if M[-1] <= last and M[0] <= last:
            break
        
        if M[-1] <= last:
            ans += ["L"]
            last = M[0]
            M.popleft()
            continue
        
        if M[0] <= last:
            ans += ['R']
            last = M[-1]
            M.pop()
            continue
        
        if M[0] <= M[-1]:
            ans += ["L"]
            last = M[0]
            M.popleft()
        elif M[-1] <= M[0]:
            ans += ["R"]
            last = M[-1]
            M.pop()

print(len(ans))
print("".join(ans)) 


n = int(input())
a = [int(i) for i in input().split()]
last = -1
i = 0
j = n - 1
ans = ''
while i <= j:
    if max(a[i], a[j]) <= last:
        break
    if a[i] < a[j]:
        if a[i] > last:
            ans += 'L'
            last = a[i]
            i += 1
        else:
            ans += 'R'
            last = a[j]
            j -= 1
    else:
        if a[j] > last:
            ans += 'R'
            last = a[j]
            j -= 1
        else:
            ans += 'L'
            last = a[i]
            i += 1
print(len(ans))
print(ans)


n = int(input())
u = list(map(int, input().split()))
i1 = 0; i2 = n - 1
ans = []
m = 0
p = []
while 1 == 1:
    m1 = min(u[i1], u[i2])
    m2 = max(u[i1], u[i2])
    if m > m2:
        break
    #print(m, m1, m2)
    if m > m1:
        p.append(m2)
        m = m2
        if u[i1] > u[i2]:
            i1 += 1
            ans.append('L')
        else:
            i2 -= 1
            ans.append('R')
    else:
        p.append(m1)
        m = m1
        if u[i1] < u[i2]:
            i1 += 1
            ans.append('L')
        else:
            i2 -= 1
            ans.append('R')
    if i1 > i2:
        break
    #print(p)
print(len(ans))
print(''.join(ans))


n = int(input())
sp = list(map(int, input().split()))
pr = 0
posl = ""
l = 0
r = n - 1
while True:
	fl = True
	if sp[l] < sp[r]:
		if sp[l] > pr:
			pr = sp[l]
			l += 1
			posl += "L"
		elif sp[r] > pr:
			pr = sp[r]
			r -= 1
			posl += "R"
		else:
			fl = False
	else:
		if sp[r] > pr:
			pr = sp[r]
			r -= 1
			posl += "R"
		elif sp[l] > pr:
			pr = sp[l]
			l += 1
			posl += "L"
		else:
			fl = False
	if not fl:
		break
print(len(posl))
print(posl)


n = int(input())
num = [*list(map(int, input().split()))]
ans = ""
current = -1
i = 0
j = n - 1
while True:
    if j < i:
        break
    if current < num[i] <= num[j] or num[j] <= current < num[i]:
        ans += "L"
        current = num[i]
        i += 1
        continue
    if current < num[j] <= num[i] or num[i] <= current < num[j]:
        ans += "R"
        current = num[j]
        j -= 1
        continue
    break
print(len(ans))
print(ans)


n = int(input())
i = 0
j = n-1
cur = 0
ls = list(map(int, input().split()))
res = []
while i<=j:
    if ls[i]>cur and ls[j]>cur:
        if ls[i]<ls[j]: res.append('L'); cur = ls[i]; i+=1
        else: res.append('R'); cur = ls[j]; j-=1
    elif ls[i]>cur: res.append('L'); cur = ls[i]; i+=1
    elif ls[j]>cur: res.append('R'); cur = ls[j]; j-=1
    else: break
print(len(res))
for i in res: print(i, end='')
print()



n = int(input())

arr = list(map(int,input().strip().split()))

fl = 1

ans = ""
c = 0

st = 0
en = n-1

la = 0

while fl:
    if arr[st] > la:
        if arr[en]>la:
            if arr[en] > arr[st]:
                st+=1
                la = arr[st-1]
                ans+="L"
                c+=1
            else:
                en-=1
                la  = arr[en+1]
                ans+="R"
                c+=1
        else:
            st+=1
            la = arr[st-1]
            ans+="L"
            c+=1
    else:
        if arr[en]>la:
            en-=1
            la =arr[en+1]
            ans+="R"
            c+=1
        else:
            break;
print(c)
print(ans)
                


n = int(input())
a = [int(item) for item in input().split()]

s = []
i = 0
j = n - 1
ans = []
while i <= j:
    if a[i] < a[j]:
        if not s or s[-1] < a[i]:
            s.append(a[i])
            ans.append('L')
            i += 1
        elif not s or s[-1] < a[j]:
            s.append(a[j])
            ans.append('R')
            j -= 1
        else:
            break
    else:
        if not s or s[-1] < a[j]:
            ans.append('R')
            s.append(a[j])
            j -= 1
        elif not s or s[-1] < a[i]:
            s.append(a[i])
            ans.append('L')
            i += 1
        else:
            break

print(len(s))
print(''.join(ans))


3

def main():
    # skip N
    input()
    a = [int(x) for x in input().split(' ')]
    n = len(a)

    l, r = 0, n - 1
    res = []
    
    last = 0
    picked = True

    while l <= r and picked:
        picked = False
        if last < a[l] and last < a[r]:
            if a[l] < a[r]:
                last = a[l]
                res.append('L')
                l += 1
            else:
                last = a[r]
                res.append('R')
                r -= 1
            picked = True
            continue
        
        if last < a[l]:
            last = a[l]
            res.append('L')
            l += 1
            picked = True
            continue
        
        if last < a[r]:
            last = a[r]
            res.append('R')
            r -= 1
            picked = True
            continue
    
    print(len(res))
    print("".join(res))
        

def __starting_point():
    main()
__starting_point()


n = int(input())

arr = list(map(int,input().strip().split()))

fl = 1

ans = ""
c = 0

st = 0
en = n-1

la = 0

while fl:
    if st>=n or en<=-1:
        break
    if arr[st] > la:
        if arr[en]>la:
            if arr[en] > arr[st]:
                st+=1
                la = arr[st-1]
                ans+="L"
                c+=1
            else:
                en-=1
                la  = arr[en+1]
                ans+="R"
                c+=1
        else:
            st+=1
            la = arr[st-1]
            ans+="L"
            c+=1
    else:
        if arr[en]>la:
            en-=1
            la =arr[en+1]
            ans+="R"
            c+=1
        else:
            break;
print(c)
print(ans)
                


import sys
from collections import deque


fin = sys.stdin.readline
n = int(fin())
a_list = deque(int(elem) for elem in fin().split())
last_elem = float('-inf')
length_sequence = 0
operations = []
while a_list:
    if last_elem < a_list[-1] <= a_list[0]:
        last_elem = a_list.pop()
        operations.append("R")
    elif last_elem < a_list[0] <= a_list[-1]:
        last_elem = a_list.popleft()
        operations.append("L")
    elif a_list[0] < last_elem < a_list[-1]:
        last_elem = a_list.pop()
        operations.append("R")
    elif a_list[-1] < last_elem < a_list[0]:
        last_elem = a_list.popleft()
        operations.append("L")
    else:
        break
    length_sequence += 1
print(length_sequence)
print("".join(operations))


n=int(input())
arr=list(map(int,input().split()))
i=0
j=n-1
ans=''
prev=0
while(i<j):
	if(arr[i]<arr[j]):
		if(arr[i]>prev):
			ans+='L'
			prev=arr[i]
			i+=1
		elif(arr[j]>prev):
			ans+='R'
			prev=arr[j]
			j-=1
		else:
			break
	elif(arr[i]>arr[j]):
		if(arr[j]>prev):
			ans+='R'
			prev=arr[j]
			j-=1
		elif(arr[i]>prev):
			ans+='L'
			prev=arr[i]
			i+=1
		else:
			break
	#print(i,j)
if(i==j and arr[i]>prev):
	ans+='R'
	prev=arr[i]
print(len(ans))
print(ans)



n = int(input())
a = list(map(int, input().split()))
l = 0
r = n - 1
ot = []
prot = ""
if a[l] < a[r]:
	ot.append(a[l])
	l += 1
	prot += "L"
else:
	ot.append(a[r])
	r -= 1
	prot += "R"
run = True
while run:
	if l > r:
		#print("A")
		run = False
	elif l == r:
		if a[l] >= ot[-1]:
			prot += "R"
		#print("B")
		run = False
	else:
		if ot[-1] <= a[l] <= a[r]:
			ot.append(a[l])
			l += 1
			prot += "L"
			#print("1")
		elif ot[-1] <= a[r] <= a[l]:
			ot.append(a[r])
			r -= 1
			prot += "R"
			#print("2")
		elif ot[-1] <= a[l]:
			ot.append(a[l])
			l += 1
			prot += "L"
			#print("3")
		elif ot[-1] <= a[r]:
			ot.append(a[r])
			r -= 1
			prot += "R"
			#print("4")
		else:
			#print("C")
			run = False
print(len(prot))
print(prot)


import math
n = int(input())
a = list(map(int, input().split()))
l = 0
r = len(a)-1
ans = []
last = -math.inf
while True:
    if l > r:
        break
    if a[l] <= a[r] and a[l] > last:
        ans.append('L')
        last = a[l]
        l += 1
    elif a[r] > last:
        ans.append('R')
        last = a[r]
        r -= 1
    elif a[l] > last:
        ans.append('L')
        last = a[l]
        l += 1
    else:
        break
print(len(ans))
print(''.join(ans))

from collections import deque
n = int(input())
a = deque(map(int, input().split()))

cnt = 0
ans = []
last = 0

while cnt < n and max(a[0], a[-1]) > last:
	cnt += 1
	if a[0] > last and (a[0] < a[-1] or a[-1] <= last):
		ans.append('L')
		last = a.popleft()
	else:
		ans.append('R')
		last = a.pop()

print(cnt)
print("".join(ans))

from collections import deque
n=int(input())
a=list(map(int,input().split()))
a=deque(a)
p=0
b=[]
for i in range(n):
    if a[0]>=a[-1] and a[-1]>p:
        # print("R",end='')
        p=a.pop()
        b.append("R")
    elif a[0]>=a[-1] and a[0]>p:
        # print("L",end='')
        p=a.popleft()
        b.append("L")
    elif a[-1]>=a[0] and a[0]>p:
        # print("L",end='')
        p=a.popleft()
        b.append("L")
    elif a[-1]>=a[0] and a[-1]>p:
        # print("R",end='')
        p=a.pop()
        b.append("R")
    else:
        break
# print()    
print(len(b))
print("".join(b))
        
    


from collections import deque

def solve(A):
    res = []
    last = 0
    while A:
        if max(A[0],A[-1]) <= last:
            return res

        if A[0] == A[-1]:
            v = A[0]-1
            for i,a in enumerate(A):
                if v < a:
                    v = a
                else:
                    break
            else:
                i += 1
            L = i
            v = A[-1]-1
            for i,a in enumerate(reversed(A)):
                if v < a:
                    v = a
                else:
                    break
            else:
                i += 1
            R = i
            _,op = max((L, ['L']*L), (R, ['R']*R))
            res.extend(op)
            return res
        
        v, op = min((v, op) for v,op in ((A[0], 'L'), (A[-1], 'R')) if v > last)
        last = v
        res.append(op)
        if op == 'L':
            A.popleft()
        else:
            A.pop()


def main():
    input()
    A = deque(map(int,input().split()))

    res = solve(A)
    print(len(res))
    print(*res, sep='')


main()

n = int(input())
row = list(map(int, input().split()))
l = 0
r = n - 1
last = 0
ans = ''
while 1:

    if row[l] < row[r]:
        if row[l] > last:
            ans += 'L'
            last = row[l]
            l += 1
        elif row[r] > last:
            ans += 'R'
            last = row[r]
            r  -= 1
        else:
            break
    else:
        if row[r] > last:
            ans += 'R'
            last = row[r]
            r -= 1
        elif row[l] > last:
            ans += 'L'
            last = row[l]
            l += 1
        else:
            break

print(len(ans))
print(ans)


from collections import deque

n = int(input())
a = deque(list(map(int, input().split())))

b = []
d = []
if a[0] < a[-1]:
    b.append('L')
    d.append(a[0])
    a.popleft()
else:
    d.append(a[-1])
    a.pop()
    b.append('R')

while a:
    c = d[-1]
    if a[0] < a[-1]:
        if c < a[0]:
            d.append(a[0])
            a.popleft()
            b.append('L')
        elif c < a[-1]:
            d.append(a[-1])
            a.pop()
            b.append('R')
        else:
            break
    else:
        if c < a[-1]:
            d.append(a[-1])
            a.pop()
            b.append('R')
        elif c < a[0]:
            d.append(a[0])
            a.popleft()
            b.append('L')
        else:
            break
print(len(b))
print(''.join(b))