Problem H
Wizard 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 |
