29085번 - Ленивцы и забор 다국어

문제

Ленивцы во главе с Блицем решили покрасить забор. Забор состоит из $n$ досок, каждая из которых изначально непокрашена.

Они собираются красить забор по следующему алгоритму: у некоторых досок встанет по одному ленивцу с краской, эти доски сразу будут покрашены, затем Блиц подаст команду сдвинуться на одну доску вправо, после выполнения этой команды каждый ленивец покрасит ту доску, напротив которой он оказался. Эта доска может быть уже покрашена, тогда ленивец напротив этой доски просто отдыхает. Всего Блиц подает несколько таких команд, возможно ноль. Также известно, что ленивцы изначально распологаются так, чтобы в результате выполнения команд не оказаться за забором, то есть перед выполнением команды никакой ленивец не должен оказаться напротив доски с номером $n$.

Блиц хочет покрасить забор определенным образом. То есть для каждой доски он знает, покрашенной она должна быть или нет после выполнения всех команд.

Пока ленивцы только собираются прийти, чтобы осуществить задумку Блица, поэтому он не знает точно, сколько их придет. Поэтому он просит вас для всех $i$ от 1ドル$ до $n$ посчитать, какого наименьшего количества команд можно достичь, если в покраске забора будут участвовать $i$ ленивцев.

입력

В первой строке содержится натуральное число $n$ (1ドル \le n \le 10^6$) --- количество досок в заборе.

В следующей строке содержится строка, состоящая из $n$ символов, каждый из которых либо '.' --- это означает, что доска должна остаться непокрашенной, либо '#' --- доска должна быть покрашенной после выполнения всех команд.

출력

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

제한

힌트