虚无存于世间。虚无有两种，这里分别记作 $0$ 和 $1$。

星，诞于虚无。虚无的规则排列称之为星，也即星为 $01$ 序列。

虚无拥有意志。星是可变的，星可以被划分成 $m$ 个部分，每个部分是原来的星中的连续一段。

世界遵从热力学第二定律。虚无的排列总是尽量规则，我们选择最长不下降子序列长度作为量度，星被划分为的 $m$ 段经过重排后，总会到达最长不下降子序列长度最大的状态。

但 $m$ 不是固定的，你需要对于每个可能的 $m$ 求出上述最长不下降子序列长度的最大值。

题目描述

给定长度为 $n$ 的 $01$ 串 $a_{1\cdots n}$，对于每个 $m∈[1,n]$ 求出：

• 将 $a_{1…n}$ 划分为 $m$ 个子段后，将子段以任意顺序拼接起来得到新序列，这个新序列的最长不下降子序列长度的最大值。

输入格式

第一行：一个整数 $n$。

第二行：一个长度为 $n$ 的 $01$ 串，第 $i$ 位表示 $a_i$。

输出格式

一行 $n$ 个整数，分别表示 $m = 1, 2, \cdots, n$ 时的答案。

样例 1

input

8
01100100

output

5 7 7 8 8 8 8 8

explanation

• $m=1$ 时划分为子段 $01100100$，最长不下降子序列为 $\underline{0}11\underline{00}1\underline{00}$。
• $m=2$ 时划分为子段 $011,00100$，拼接为 $00100011$，最长不下降子序列为 $\underline{00}1\underline{00011}$。
• $m=3$ 时划分为子段 $011,001,00$，拼接为 $00001011$，最长不下降子序列为 $\underline{00001}0\underline{11}$。
• $m=4$ 时划分为子段 $011,00,1,00$，拼接为 $00000111$，最长不下降子序列为 $\underline{00000111}$。
• $m>4$ 时子段拼接结果与 $m=4$ 相同。注意上面展示的划分，拼接方案与最长不下降子序列都可能不是唯一的。

样例 2

input

20
10110001010110001101

output

12 14 14 16 16 17 17 18 18 19 19 20 20 20 20 20 20 20 20 20

子任务

对于全部数据：$1≤n≤3×10^5$。

Subtask 1 (15 pts)：$n≤8$。

Subtask 2 (15 pts)：$n≤20$。

Subtask 3 (15 pts)：$n≤200$。

Subtask 4 (20 pts)：$n≤2\,000$。

Subtask 5 (20 pts)：$n≤80\,000$。

Subtask 6 (15 pts)：无特殊限制。