题目描述

给定一个由 o 和 x 组成的长度为 $N$ 的字符串 $S$。

有 $N$ 个袋子排成一列，每个袋子里装着 $1$ 颗糖。第 $i$ 个袋子上：若 $S$ 的第 $i$ 个字符是 o，写着「中奖」；是 x 则写着「未中奖」。

对每个 $k = 1, 2, \ldots, N$，请解决下面的问题：

高橋君先从队列最前面拿走 $k$ 个袋子，把里面的糖都吃掉，袋子留着。

之后，他尽可能多地重复下面的操作：

• 丢掉手上一个写着「中奖」的袋子，然后从队列最前面再拿一个袋子，吃掉里面的糖，并把这个袋子留着。

该操作只有在队列里还有袋子且手上还有「中奖」袋子时才能进行。

请求出高橋君一共能吃到多少颗糖。

注意：袋子一旦被拿走，就从队列中移除了。

输入格式

N
S

输出格式

输出 $N$ 行，第 $l$ 行是 $k = l$ 时的答案。

输入示例 1

5
oxoxo

输出示例 1

2
4
5
5
5

示例 1 说明

以 $k = 1$ 为例：先拿走第 $1$ 个袋子（o，中奖），吃掉 $1$ 颗糖，手上有 $1$ 个中奖袋。

丢掉它，再拿第 $2$ 个袋子（x，未中奖），吃掉第 $2$ 颗糖。此时手上已经没有中奖袋，无法继续，共吃 $2$ 颗。

以 $k = 2$ 为例：先拿前 $2$ 个（o,x），吃 $2$ 颗，手上有 $1$ 个中奖袋。丢掉它拿第 $3$ 个（o），吃第 $3$ 颗，手上又有 $1$ 个中奖袋；丢掉它拿第 $4$ 个（x），吃第 $4$ 颗，手上没有中奖袋了，共吃 $4$ 颗。

输入示例 2

3
ooo

输出示例 2

3
3
3

示例 2 说明

全是中奖袋，所以只要队列里还有袋子就能一直拿下去，最终 $3$ 个袋子全部吃完。

输入示例 3

1
x

输出示例 3

1

示例 3 说明

只有一个袋子且写着「未中奖」。$k = 1$ 时拿走它、吃掉糖，手上没有中奖袋，也没有袋子可拿了，共吃 $1$ 颗。

约束条件

• $1 \le N \le 8 \times 10^5$
• $N$ 是整数
• $S$ 是由 o 和 x 组成的长度为 $N$ 的字符串