D - LR insertion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

1 個の 0 のみからなる数列 A=(0) があります。
また、L と R のみからなる長さ N の文字列 S=s_1s_2\ldots s_N が与えられます。

i=1,2,\ldots ,N の順番で、次の操作を行います。

  • s_i が L のとき、A 内にある i-1 のすぐ左に i を挿入する
  • s_i が R のとき、A 内にある i-1 のすぐ右に i を挿入する

最終的な A を求めてください。

制約

  • 1\leq N \leq 5\times 10^5
  • N は整数である
  • |S| = N
  • s_i は L か R のいずれかである

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

最終的な A を空白区切りで出力せよ。

入力例 1

5
LRRLR

出力例 1

1 2 4 5 3 0

はじめ、A=(0) です。
s_1 が L なので、A=(1,0) となります。
s_2 が R なので、A=(1,2,0) となります。
s_3 が R なので、A=(1,2,3,0) となります。
s_4 が L なので、A=(1,2,4,3,0) となります。
s_5 が R なので、A=(1,2,4,5,3,0) となります。

入力例 2

7
LLLLLLL

出力例 2

7 6 5 4 3 2 1 0

Score : 400 points

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

  • If s_i is L, insert i to the immediate left of i-1 in A.
  • If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

  • 1\leq N \leq 5\times 10^5
  • N is an integer.
  • |S| = N
  • s_i is L or R.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the final contents of A, separated by spaces.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0