Controversial Rounds

题意翻译

【题目描述】 Alice和Bob在玩游戏。整个游戏过程包含若干**组**游戏。每一**组**游戏会进行若干**轮**。在每一**轮**游戏中，要么Alice赢要么Bob赢。一**组**游戏结束，当且仅当Alice和Bob中的`1`个人在这一**组**游戏中赢了**连续**的`x`**轮**。 你现在知道，Alice和Bob一共进行了`n`**轮**游戏，并且知道其中若干**轮**游戏的结果。 对于每一个`x`（`x`的定义在上文，且`1<=x<=n`），要求你计算出Alice和Bob能进行的游戏**组**数的最大值。如果在一种方案中，最后一**组**游戏并不能刚好结束，那么这组游戏不计入该方案。 【输入格式】 第一行包括一个整数`n`（`1<=n<=1000000`），表示Alice和Bob进行的游戏**轮**数。 第二行包括一个长度为`n` 的字符串`s`，如果`s`的第`i`位为`0`，那么Alice就赢了第`i`**轮**游戏，如果为`1`，那么就是Bob赢，如果为`?`，就表示你并不知道第`i`**轮**游戏的胜负情况。 【输出格式】 一行，包括`n`个整数，第`i`个整数表示当`x=i`时的答案。

题目描述

Alice and Bob play a game. The game consists of several sets, and each set consists of several rounds. Each round is won either by Alice or by Bob, and the set ends when one of the players has won $ x $ rounds in a row. For example, if Bob won five rounds in a row and $ x = 2 $ , then two sets ends. You know that Alice and Bob have already played $ n $ rounds, and you know the results of some rounds. For each $ x $ from $ 1 $ to $ n $ , calculate the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $ x $ rounds in a row. It is possible that the last set is still not finished — in that case, you should not count it in the answer.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the number of rounds. The second line contains one string $ s $ of length $ n $ — the descriptions of rounds. If the $ i $ -th element of the string is 0, then Alice won the $ i $ -th round; if it is 1, then Bob won the $ i $ -th round, and if it is ?, then you don't know who won the $ i $ -th round.

输出格式

In the only line print $ n $ integers. The $ i $ -th integer should be equal to the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $ i $ rounds in a row.

输入输出样例

输入样例 #1

6
11?000

输出样例 #1

6 3 2 1 0 0

输入样例 #2

5
01?01

输出样例 #2

5 1 0 0 0

输入样例 #3

12
???1??????1?

输出样例 #3

12 6 4 3 2 2 1 1 1 1 1 1

说明

Let's consider the first test case: - if $ x = 1 $ and $ s = 110000 $ or $ s = 111000 $ then there are six finished sets; - if $ x = 2 $ and $ s = 110000 $ then there are three finished sets; - if $ x = 3 $ and $ s = 111000 $ then there are two finished sets; - if $ x = 4 $ and $ s = 110000 $ then there is one finished set; - if $ x = 5 $ then there are no finished sets; - if $ x = 6 $ then there are no finished sets.