OpenKattis
Baylor University

# Wizard Dance

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