C - Cantrip 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

o と x からなる長さ N の文字列 S が与えられます。
N 個の袋が一列に並んでいて、各袋にはお菓子が 1 個ずつ入っています。
i 番目の袋には、S の i 文字目が o ならば「当たり」と書かれており、x ならば「はずれ」と書かれています。
k=1,2,\dots,N について以下の問題を解いてください。

高橋君は列の先頭から k 個の袋を受け取り、入っているお菓子を食べ、袋は持っておきます。
その後、以下の行動を可能な限り繰り返します。

  • 高橋君が持っている「当たり」と書かれた袋を 1 個捨て、列の先頭の袋を受け取り、中のお菓子を食べてその袋を持っておく。ただし、列にまだ袋が残っていて、かつ「当たり」と書かれた袋を持っている場合にしか行動はできない。
高橋君が食べることのできるお菓子の個数を求めてください。
袋を受け取った場合、その袋は列から取り除かれることに注意してください。

制約

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

入力

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

N  
S

出力

答えを合計 N 行で出力せよ。
l 行目には、k=l のときの答えを出力せよ。

入力例 1

5
oxoxo

出力例 1

2
4
5
5
5

k=1 のとき、受け取った袋には「当たり」と書かれています。 それを捨てて受け取った袋には「はずれ」と書かれており、それ以上の行動はできません。

入力例 2

3
ooo

出力例 2

3
3
3

入力例 3

1
x

出力例 3

1

Score : 300 points

Problem Statement

You are given a string S of length N consisting of o and x.
N bags are arranged in a row, and each bag contains one sweet.
On the i-th bag, "hit" is written if the i-th character of S is o, and "miss" is written if it is x.
For each k=1,2,\dots,N, solve the following problem.

Takahashi receives the first k bags from the front of the row, eats the sweets inside them, and keeps the bags.
Then, he repeats the following action as many times as possible.

  • He discards one bag marked "hit" that he is holding, receives the bag at the front of the row, eats the sweet inside it, and keeps that bag. This action can only be performed when there is still a bag remaining in the row and he is holding a bag marked "hit".
Find the number of sweets he can eat.
Note that when he receives a bag, that bag is removed from the row.

Constraints

  • 1 \leq N \leq 8 \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 a total of N lines.
The l-th line should contain the answer for k=l.

Sample Input 1

5
oxoxo

Sample Output 1

2
4
5
5
5

For k=1, the bag he receives is marked "hit". He discards it, and the bag he then receives is marked "miss", so he cannot perform any further actions.

Sample Input 2

3
ooo

Sample Output 2

3
3
3

Sample Input 3

1
x

Sample Output 3

1