题目内容

小红有一个长度为 $n$、仅由$0$和$1$构成的字符串$s$，下标从$1$开始。

请你输出对每个位置上的字符反置后，新的字符串中全部"$01$"子序列的数量。

注意，操作是彼此独立的，对于前一个位置的反置不会影响到对当前位置的反置。

若当前字符为 $0$，反置后为$1$;若当前字符为$1$，反置后为$0$。

"$01$"子序列是从长度为$n$的字符串中任意删除$n-2$个字符所得到的字符串，且该字符串恰好为"$01$"

输入描述

第一行输入一个整数 $n(1 ≤ n ≤ 10^5)$表示字符串长度。

第二行输入一个长度为$n$、仅由 $0$ 和$1$构成的字符串 $s$。

输出描述

在一行上输出$n$个整数，第$i$个数表示把$s_i$反置后得到的新字符串中，"$01$"子序列的数量。

样例1

输入

5
00101

输出

3 4 4 6 2

说明

将第一个位置反置后得到$s= 10101$，一共有三个 $01$ 子序列，分别是:10101、10101和10101