시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB59413063.830%

문제

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 ≤ n ≤ 2 · 105) 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.

예제 입력 1

3
LR

예제 출력 1

2
1
3

예제 입력 2

6
RLLRL

예제 출력 2

1
4
3
2
6
5

예제 입력 3

6
RRRLL

예제 출력 3

1
2
3
6
5
4

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2018 G번

  • 문제를 만든 사람: Bowen Yu