Dãy con tăng ngặt (khó)

Cho một dãy $a$ gồm $n$ số nguyên dương.

Bạn thực hiện một chuỗi các bước. Trong mỗi bước, bạn phải lấy phần tử ngoài cùng bên trái hoặc phần tử ngoài cùng bên phải của dãy, ghi lại giá trị và xoá phần tử đó khỏi dãy.

Nhiệm vụ của bạn là thu được một dãy các giá trị tăng ngặt (mỗi số ghi sau phải lớn hơn tất cả các số đã ghi trước đó). Trong tất cả các dãy tăng ngặt có thể tạo được, hãy chọn dãy có độ dài lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên $n$ — số phần tử của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Dòng thứ nhất in ra $k$ — độ dài lớn nhất của dãy tăng ngặt có thể lấy được.
• Dòng thứ hai in ra một xâu $s$ có độ dài $k$, trong đó ký tự thứ $j$ là L nếu ở bước thứ $j$ bạn lấy phần tử ngoài cùng bên trái, hoặc R nếu bạn lấy phần tử ngoài cùng bên phải.

Nếu có nhiều đáp án khác nhau, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le 2·{10}^5$

Ví dụ