In the USA, a type of dance called square dance is very popular. Four dancing pairs stand as to form a square. A caller then gives a series of moves that the dancers should perform, moving around on the floor.

American wizards, however, find square dancing a bit simplistic. Instead, they have come up with a kind of dance called circle dancing. In the dance, $N$ wizards stand in a circle numbered $1$ through $N$ clockwise. A caller then gives a series of moves that the dancers should perform, moving around on the floor. Each such move has the following form. Every wizard is given a number $p_ i$. They then all teleport simultaneously $p_ i$ positions clockwise or counterclockwise in the ring. For example, given the number 1 they should move to one of the two places immediately adjacent to their current position.

After a move is performed, no two wizards may occupy the same position. This means a certain amount of coordination is required when teleporting. Can you tell the wizards how they should teleport in order to not collide with each other?

-----Input-----
The first line of input contains a single integer $N$ ($1 \le N \le 300000$), the number of wizards. The next line contains the $N$ integers $p_1, p_2, \dots , p_ N$ ($0 \le p_ i < N$). The wizards are numbered $1, 2, \dots , N$ clockwise in the circle.

-----Output-----
Output a string with $N$ characters. The $i$’th character should be L if the $i$’th wizard should teleport clockwise, and R if he should teleport counterclockwise. If there are multiple valid solutions, output the lexicographically smallest one. If there is no valid solution, output no dance.

-----Examples-----
Sample Input 1:
3
1 1 1
Sample Output 1:
LLL

Sample Input 2:
5
1 2 2 1 2
Sample Output 2:
LLRLR

Difficulty: competition

Starter code:

Solutions: