Wzdłuż rzeki znajduje się n miast. Pomiędzy każdą parą sąsiednich miast wybudowana jest droga, niestety nie zawsze dwukierunkowa, dlatego nie zawsze da się dojechać z każdego miasta do wszystkich innych. Znając, które drogi są wybudowane, chcielibyśmy wiedzieć dla każdego miasta, do ilu innych miast da się z niego dojechać.

입력 형식

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę miast.</p>

W kolejnym wierszu znajduje się n - 1 liczb całkowitych d₁, d₂, ..., d_n-1 (0 ≤ d_i ≤ 2), gdzie d_i oznacza połączenie pomiędzy miastem i-tym, a i+1-wszym. Jeśli:

• d_i = 0, to z miasta i-tego biegnie jednokierunkowa droga do miasta i+1-wszego,
• d_i = 1, to z miasta i+1-wszego biegnie jednokierunkowa droga do miasta i-tego,
• d_i = 2, to miasta i-te i i+1-wsze połączone są drogą dwukierunkową.

W pierwszym i jedynym wierszu wyjścia powinno znajdować się n liczb całkowitych w₁, w₂, ..., w_n, gdzie w_i oznacza liczbę miast, do których da się dojechać z miasta i-tego.

예제 입력

5
0 2 0 1

예제 출력

3 2 2 0 1