Cities

Interview

Time limit1sMemory limit128 MB

Summary

Count for each city on a directed line how many other cities are reachable through one-way and two-way roads.

Level: Medium5 of 10
Topics: Array, Prefix sum
Solved: No attempts yet

Problem

There are $n$ cities lined up along a river. Between every pair of adjacent cities exactly one road is built, but not every road is two-way, so you cannot always travel from a given city to all of the others.

Given which roads are built, determine for each city how many other cities are reachable from it.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ), the number of cities.

The second line contains $n - 1$ integers $d_1, d_2, \dots, d_{n-1}$ ( $0 \le d_i \le 2$ ), where $d_i$ describes the road between city $i$ and city $i+1$ :

if $d_i = 0$ , there is a one-way road from city $i$ to city $i+1$ ;
if $d_i = 1$ , there is a one-way road from city $i+1$ to city $i$ ;
if $d_i = 2$ , the two cities are joined by a two-way road.

Output

Print $n$ integers $w_1, w_2, \dots, w_n$ on a single line, separated by spaces, where $w_i$ is the number of cities reachable from city $i$ , not counting city $i$ itself.

Examples3

Example 1
Input
```
5
0 2 0 1
```
Expected output
```
3 2 2 0 1
```
Example 2
Input
```
4
0 0 0
```
Expected output
```
3 2 1 0
```
Example 3
Input
```
4
1 1 1
```
Expected output
```
0 1 2 3
```