Wizard Dance

A circle dance

Author: unknown, no known restrictions

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?

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 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 |