Left and Right

Image from
Pixabay

With modern technology advancement, it is now possible to deliver mail with a robot! There is a neighborhood on a long horizontal road, on which there are $n$ houses numbered $1$ to $n$ from left to right. Every day a mail delivery robot receives a pile of letters with exactly one letter for each house. Due to mechanical restrictions, the robot cannot sort the letters. It always checks the letter on top of the pile, visits the house that should receive that letter and delivers it. The robot repeats this procedure until all the letters are delivered. As a result, each of the $n$ houses is visited by the robot exactly once during the mail delivery of a single day.

The mail delivery robot has a tracking device that records
its delivery route. One day the device was broken, and the
exact route was lost. However, the technical team managed to
recover the *moving directions* of the robot
from the broken device, which are represented as a string
consisting of $n-1$
letters. The $i$-th letter
of the string is ‘`L`’ (or ‘`R`’) if the $(i+1)$-th house visited by the robot
is on the left (or right) of the $i$-th house visited. For example, if
$n = 4$ and the robot
visited the houses in the order of $2, 4, 3, 1$, its moving directions
would be “`RLL`”.

With the moving directions, it may be possible to determine the order in which the robot visited the houses. The technical team has asked you to write a program to do that. There can be multiple orders producing the same moving directions, among which you should find the lexicographically earliest order.

The input has a single integer $n$ ($2
\leq n \leq 2 \cdot 10^5$) on the first line. The second
line has a string of length $n-1$ consisting of letters
‘`L`’ and ‘`R`’ giving the
moving directions of the robot.

Output the lexicographically earliest order in which the robot may have visited the houses and delivered the letters according to the moving directions. Consider two different integer sequences of equal length $A = (a_1, a_2, \ldots , a_ k)$ and $B = (b_1, b_2, \ldots , b_ k)$, and let $1 \le i \le k$ be the lowest-numbered index where $a_ i \ne b_ i$. Then $A$ is lexicographically earlier than $B$ if $a_ i < b_ i$; otherwise $B$ is lexicographically earlier than $A$.

Sample Input 1 | Sample Output 1 |
---|---|

3 LR |
2 1 3 |

Sample Input 2 | Sample Output 2 |
---|---|

6 RLLRL |
1 4 3 2 6 5 |

Sample Input 3 | Sample Output 3 |
---|---|

6 RRRLL |
1 2 3 6 5 4 |