C - Reverse Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 N と o と x からなる長さ N の文字列 S が与えられます。

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。はじめ A=(1,2,\ldots,N) です。

A に対して k=1,2,\ldots,N の順に以下の操作を行います：

  • S_k= o である場合、A の先頭 k 項を反転する。具体的には、A を (A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N) に置き換える。
  • S_k= x である場合は何もしない。

全ての操作を終えた後の A を求めてください。

制約

  • 2\le N\le 5\times 10^5
  • N は整数
  • S は o と x からなる長さ N の文字列

入力

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

N
S

出力

全ての操作を終えた後の A の各要素を空白区切りで出力せよ。

入力例 1

5
ooxoo

出力例 1

5 2 1 3 4

A は各操作で以下のように変化します：

  • k=1 のとき：A の先頭 1 項を反転する。A=(1,2,3,4,5) になる。
  • k=2 のとき：A の先頭 2 項を反転する。A=(2,1,3,4,5) になる。
  • k=3 のとき：何もしない。
  • k=4 のとき：A の先頭 4 項を反転する。A=(4,3,1,2,5) になる。
  • k=5 のとき：A の先頭 5 項を反転する。A=(5,2,1,3,4) になる。

全ての操作を終えた後の A は A=(5,2,1,3,4) です。

入力例 2

7
ooooooo

出力例 2

7 5 3 1 2 4 6

入力例 3

15
xooxoxoxoxoxxoo

出力例 3

15 11 10 7 6 3 1 2 4 5 8 9 12 13 14

Score : 300 points

Problem Statement

You are given an integer N and a string S of length N consisting of o and x.

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Initially, A=(1,2,\ldots,N).

Perform the following operation on A for k=1,2,\ldots,N in this order.

  • If S_k= o, reverse the first k terms of A. Specifically, replace A with (A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N).
  • If S_k= x, do nothing.

Find A after all the operations are completed.

Constraints

  • 2\le N\le 5\times 10^5
  • N is an integer.
  • S is a string of length N consisting of o and x.

Input

The input is given from Standard Input in the following format:

N
S

Output

Output the elements of A after all the operations are completed, separated by spaces.

Sample Input 1

5
ooxoo

Sample Output 1

5 2 1 3 4

A changes as follows with each operation:

  • For k=1: reverse the first 1 term of A. A becomes (1,2,3,4,5).
  • For k=2: reverse the first 2 terms of A. A becomes (2,1,3,4,5).
  • For k=3: do nothing.
  • For k=4: reverse the first 4 terms of A. A becomes (4,3,1,2,5).
  • For k=5: reverse the first 5 terms of A. A becomes (5,2,1,3,4).

After all the operations are completed, A is A=(5,2,1,3,4).

Sample Input 2

7
ooooooo

Sample Output 2

7 5 3 1 2 4 6

Sample Input 3

15
xooxoxoxoxoxxoo

Sample Output 3

15 11 10 7 6 3 1 2 4 5 8 9 12 13 14