F. Спорные раунды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. Игра состоит из нескольких сетов, и каждый сет состоит из нескольких раундов. Каждый раунд выиграл либо Боб, либо Алиса, и сет считается завершенным, когда один из игроков выиграл $$$x$$$ раундов подряд. Например, если Боб выиграл пять раундов подряд и $$$x = 2$$$, то завершилось два сета.

Вы знаете, что Алиса и Боб уже сыграли $$$n$$$ раундов и вы знаете результаты нескольких раундов. Для каждого $$$x$$$ от $$$1$$$ до $$$n$$$, посчитайте максимальное количество сетов, которое могло быть завершено, если сет считается завершенным, когда один из игроков выиграл $$$x$$$ раундов подряд. Если последний сет не завершен — то учитывать его не нужно.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество раундов.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$ — описание раундов. Если $$$i$$$-й элемент строки равен 0, то Алиса выиграла $$$i$$$-й раунд; если равен 1 — то Боб выиграл $$$i$$$-й раунд, а если равен ? — то вы не знаете, кто выиграл $$$i$$$-й раунд.

Выходные данные

В единственной строке выведите $$$n$$$ чисел. $$$i$$$-е должно быть равно максимальному количество сетов, которое могло быть завершено, если сет считается завершенным когда один из игроков выиграл $$$i$$$ раундов подряд.

Примеры
Входные данные
6
11?000
Выходные данные
6 3 2 1 0 0
Входные данные
5
01?01
Выходные данные
5 1 0 0 0
Входные данные
12
???1??????1?
Выходные данные
12 6 4 3 2 2 1 1 1 1 1 1
Примечание

Рассмотрим первый набор входных данных:

  • если $$$x = 1$$$ и $$$s = 110000$$$ или $$$s = 111000$$$ то есть шесть завершенных сетов;
  • если $$$x = 2$$$ и $$$s = 110000$$$ то есть три завершенных сета;
  • если $$$x = 3$$$ и $$$s = 111000$$$ то есть два завершенных сета;
  • если $$$x = 4$$$ и $$$s = 110000$$$ то есть один завершенный сет;
  • если $$$x = 5$$$ то завершенных сетов нет;
  • если $$$x = 6$$$ то завершенных сетов нет.