题目内容

在一个二进制传输实验中，工程师记录了一段长度为 $n$ 的信号序列，序列中每个位置要么为 0 (表示低电平)，要么为 1 (表示高电平)。

在分析信号时，一对先 0 后 1 的有序下标被称为一个“增长对”。具体来说，若存在下标 $i<j$ 满足序列第 $i$ 位为 0 且第 $j$ 位为 1，则 $(i,j)$ 构成一个增长对。

现在工程师想要评估每个位置的重要性，因此他进行如下操作：对于第 $k$ 个位置 ($1 \le k \le n$)，单独将该位置的信号取反（0 变为 1，1 变为 0），其他位置不变，然后计算此时整个序列中增长对的总数。这一操作是独立的，即每次只翻转一个位置，并立即统计该状态下的结果。

请你为每个位置输出翻转后对应的增长对数量。

序列的长度 $n$ 满足 $1 \le n \le 10^5$。序列中仅包含字符 0 和 1。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列的长度。

第二行包含一个长度为 $n$ 的字符串，仅由字符 0 和 1 组成，表示原始的信号序列。

输出描述

在一行上输出 $n$ 个整数，两两之间用一个空格隔开。第 $i$ 个整数表示将第 $i$ 个位置的字符翻转后，整个序列中增长对的数量。

样例1

输入

1
0

输出

0

说明

序列长度为 1，仅有一个位置。将其翻转后变为 1。由于不存在两个不同的下标 $i < j$，因此增长对的数量为 $0$。

样例2

输入

2
01

输出

0 0

说明

原始序列 "01" 中，唯一的增长对是 $(1,2)$。翻转第 1 个位置变为 "11"，没有 0，增长对数量为 $0$；翻转第 2 个位置变为 "00"，没有 1，增长对数量也为 $0$。因此输出 0 0。

样例3

输入

4
1010

输出

2 0 0 2

说明

原始序列 "1010" 的增长对数量为 $1$（仅 $(2,3)$）。翻转位置 1 变为 "0010"，增长对为 $(1,3)$ 和 $(2,3)$，共 $2$ 个；翻转位置 2 变为 "1110"，没有 $0$ 出现在 $1$ 之前，数量为 $0$；翻转位置 3 变为 "1000"，同样为 $0$；翻转位置 4 变为 "1011"，增长对为 $(2,3)$ 和 $(2,4)$，共 $2$ 个。因此输出 2 0 0 2。

样例4

输入

4
0000

输出

0 1 2 3

说明

原始全 0 序列的增长对数量为 $0$。翻转第 $k$ 个 0 后，该位置变成 1，左侧的 $k-1$ 个 0 均可以与这个新 1 构成增长对，右侧的 0 不能作为前项。因此翻转第 1,2,3,4 个位置时，增长对数量分别为 $0,1,2,3$。