MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

II Copa MATCOM ACM-ICPC

Ended

I - Bus

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Isla Bella es un país con un sistema de transporte peculiar. La Isla cuenta solamente con un autobús llamado $A1$ y un sistema de $K + 1$ paradas convenientemente numeradas de $0$ a $K$. Todas las mañanas $A1$ recoge a $N$ personas en la parada $0$ y realiza su viaje pasando en orden por las paradas $1, 2, \dotsc, K$. Cada una de las $N$ personas desea quedarse en una de las $K$ paradas $1, 2, \dotsc, K$.

El autobús $A1$ es muy incómodo porque no tiene asientos; además, es tan estrecho, que las personas deben viajar una pegada a la otra. $A1$ tiene solamente dos puertas, una al principio (izquierda) y otra al final (derecha).

Al llegar a una parada, algunas personas se bajarán del autobús por una de las dos puertas. Cuando esto sucede hay muchas molestias en $A1$, porque las personas se deben abrir paso hasta poder salir. Se dice que hay una molestia si una persona tiene que pasar por detrás de otra para poder salir.

Con el objetivo de minimizar las molestias durante el viaje deseamos calcular cuál puerta usará cada pasajero para dejar el autobús. Por ejemplo:

Supongamos que $N = 7$ y $K = 4$. Las personas se bajarán del autobús en las paradas $[4, 3, 1, 2, 3, 1, 4]$.

Parada

Autobús

Descripción

0

[4, 3, 1, 2, 3, 1, 4]

Las 7 personas suben al autobús.

1

[4, 3, 1 , 2, 3, 1 , 4]

- La tercera persona se baja por la puerta del fondo (izquierda en el dibujo).

- La sexta persona se baja por la puerta al inicio (derecha en el dibujo)

Molestias : (1, 3), (2, 3), (6, 7)

2

[4, 3, __, 2 , 3, __, 4]

- La cuarta persona se baja por la puerta izquierda.

Molestias : (1, 4), (2, 4)

3

[4, 3 , __, __, 3 , __, 4]

- La segunda persona se baja por la derecha.

- La quinta persona se baja por la izquierda.

Molestias : (1, 5), (2, 5), (2, 7)

4

[ 4 , __, __, __, __, __ 4 ]

- La primera persona se baja por la derecha.

- La séptima persona se baja por la izquierda.

Molestias : (1, 7)

Con la distribución anterior ocurren 9 molestias, no obstante existe una planificación mejor.

Input

Línea 1 : Dos enteros $N$ y $K$ separados por espacio $(1 \le N \le 200000, 1 \le K \le 10^9)$.
Línea 2 : $N$ enteros separados por espacio $P_1, P_2, \dotsc, P_N$ representando las paradas donde cada pasajero debe quedarse. Los pasajeros están ubicados de izquierda a derecha numerados desde $1$ hasta $N$ $(1 \le P_i \le K)$.

Output

Línea 1 : Una cadena de longitud $N$ conteniendo solamente los caracteres ‘L’ y ‘R’ representando un plan que minimice las molestias durante el recorrido de $A1$. Si el $i$-ésimo carácter es ‘L’ entonces la $i$-ésima persona utilizará la puerta de la izquierda, si el carácter es ‘R’ entonces usará la puerta de la derecha. Si múltiples soluciones existen, entonces imprima una de ellas.

Sample test(s)

Input
7 4 4 3 1 2 3 1 4
Output
LLLLLRL

Hints

La cantidad mínima de molestias para el ejemplo es 7.