시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 3 2 66.667%

문제

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 ≤ 106), oznaczającą liczbę miast.

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

  • di = 0, to z miasta i-tego biegnie jednokierunkowa droga do miasta i+1-wszego,
  • di = 1, to z miasta i+1-wszego biegnie jednokierunkowa droga do miasta i-tego,
  • di = 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 w1, w2, ..., wn, gdzie wi oznacza liczbę miast, do których da się dojechać z miasta i-tego.

예제 입력 1

5
0 2 0 1

예제 출력 1

3 2 2 0 1