You are give a binary string \(S\) of length \(N\) containing only 0's and 1's. For each index \(i\) (\(1 \le i \le N\)), what is the length of the longest substring in \(S\) that includes index \(i\) and consists only of 1's? The length could be 0.

Input Specification

The first line will contain the integer \(N\) (\(1 \le N \le 2 \times 10^5\)). The second line contains the list of \(N\) integers.

Output Specification

Print \(N\) space-separated integers: the answer for each index \(i\).

Sample Input

6
101100

Sample Output

1 0 2 2 0 0