CF1398F.Controversial Rounds

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.

爱丽丝和鲍勃进行一场比赛。比赛由若干局组成，每局又由若干轮组成。每轮由爱丽丝或鲍勃中的一方获胜，当某一方连续赢得 $x$ 轮时，该局即告结束。例如，若鲍勃连续赢了五轮，且 $x = 2$，则共结束了两局。

已知爱丽丝和鲍勃已经进行了 $n$ 轮比赛，且已知其中部分轮次的结果。对每个从 $1$ 到 $n$ 的 $x$，计算在每局均持续至某一方连续赢得 $x$ 轮的前提下，目前已可能结束的最大局数。注意：最后一局可能尚未结束——此时不应将其计入答案。

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.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示回合数。

第二行包含一个长度为 $n$ 的字符串 $s$ —— 表示各回合的结果描述。若字符串的第 $i$ 个字符为 0，则 Alice 赢得了第 $i$ 回合；若为 1，则 Bob 赢得了第 $i$ 回合；若为 ?，则第 $i$ 回合的获胜者未知。

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.

在唯一的一行中输出 $n$ 个整数。其中第 $i$ 个整数应等于：当每局比赛持续到有一名选手连续赢得 $i$ 轮时，可能已经结束的比赛局数的最大值。

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.

我们考虑第一个测试用例：

• 若 $x = 1$ 且 $s = 110000$ 或 $s = 111000$，则存在六个完成集合；
• 若 $x = 2$ 且 $s = 110000$，则存在三个完成集合；
• 若 $x = 3$ 且 $s = 111000$，则存在两个完成集合；
• 若 $x = 4$ 且 $s = 110000$，则存在一个完成集合；
• 若 $x = 5$，则不存在完成集合；
• 若 $x = 6$，则不存在完成集合。