Алиса и Боб играют в игру. Игра состоит из нескольких сетов, и каждый сет состоит из нескольких раундов. Каждый раунд выиграл либо Боб, либо Алиса, и сет считается завершенным, когда один из игроков выиграл \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач