虚无存于世间。虚无有两种,这里分别记作 0 和 1。
星,诞于虚无。虚无的规则排列称之为星,也即星为 01 序列。
虚无拥有意志。星是可变的,星可以被划分成 m 个部分,每个部分是原来的星中的连续一段。
世界遵从热力学第二定律。虚无的排列总是尽量规则,我们选择最长不下降子序列长度作为量度,星被划分为的 m 段经过重排后,总会到达最长不下降子序列长度最大的状态。
但 m 不是固定的,你需要对于每个可能的 m 求出上述最长不下降子序列长度的最大值。
题目描述
给定长度为 n 的 01 串 a1⋯n,对于每个 m∈[1,n] 求出:
- 将 a1…n 划分为 m 个子段后,将子段以任意顺序拼接起来得到新序列,这个新序列的最长不下降子序列长度的最大值。
输入格式
第一行:一个整数 n。
第二行:一个长度为 n 的 01 串,第 i 位表示 ai。
输出格式
一行 n 个整数,分别表示 m=1,2,⋯,n 时的答案。
样例 1
input
8
01100100
output
5 7 7 8 8 8 8 8
explanation
- m=1 时划分为子段 01100100,最长不下降子序列为 0_1100_100_。
- m=2 时划分为子段 011,00100,拼接为 00100011,最长不下降子序列为 00_100011_。
- m=3 时划分为子段 011,001,00,拼接为 00001011,最长不下降子序列为 00001_011_。
- m=4 时划分为子段 011,00,1,00,拼接为 00000111,最长不下降子序列为 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×105。
Subtask 1 (15 pts):n≤8。
Subtask 2 (15 pts):n≤20。
Subtask 3 (15 pts):n≤200。
Subtask 4 (20 pts):n≤2000。
Subtask 5 (20 pts):n≤80000。
Subtask 6 (15 pts):无特殊限制。