Hide

Problem E
Wizard Dance

/problems/wizarddance/file/statement/en/img-0001.jpg
A circle dance
Author: unknown, no known restrictions

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 300\, 000$), 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.

Sample Input 1 Sample Output 1
3
1 1 1
LLL
Sample Input 2 Sample Output 2
5
1 2 2 1 2
LLRLR
Sample Input 3 Sample Output 3
4
1 2 1 2
no dance

Please log in to submit a solution to this problem

Log in