자전거 묘기

길이가 $N$미터인 직선 자전거 도로가 있다. 도로는 길이가 1미터인 $N$개의 칸으로 나뉘어 있고, 가장 왼쪽 칸부터 순서대로 1번 칸, 2번 칸, …, $N$번 칸이다.

도로의 각 칸에는 점프대가 설치되어 있을 수 있다. $i$번 칸에 설치된 점프대의 높이를 $h_i$라고 하자. 높이가 $h_i$인 점프대를 밟으면 다른 요인과 관계없이 다음 $h_i$칸 위를 비행한 뒤 그다음 칸에 착지한다. 다음 예시를 확인해 보자.

자전거를 타고 1번 칸에서 출발해 앞으로 달리면 다음 일이 순서대로 일어난다.

1. 1번 칸에는 점프대가 없으므로 2번 칸으로 주행한다.
2. 2번 칸에 높이가 1인 점프대가 있어 3번 칸 위를 비행하고 4번 칸에 착지한다.
3. 4번 칸에 높이가 2인 점프대가 있어 5번 칸과 6번 칸 위를 비행하고 7번 칸에 착지한다.
4. 7번 칸에는 점프대가 없으므로 8번 칸으로 주행한다.
5. 8번 칸에 높이가 3인 점프대가 있어 9번 칸 위를 비행하여 저 멀리 나아간다. (도로가 충분히 길었다면 가상의 12번 칸에 착지하였을 것이다.)

시은이는 각 칸에서 자전거를 타고 출발해 앞으로 달릴 때 도로 위에서 몇 개의 칸을 밟게 되는지 알고 싶어 한다. $N$개의 칸을 하나씩 실험하기는 너무 번거롭다. 시은이는 아래 표를 만들어 보고, 어떤 칸의 답을 그 오른쪽 칸의 답으로부터 구할 수 있다는 것을 알아냈다.

1번 칸에는 점프대가 없으므로 그 답은 2번 칸의 답에 1을 더한 값이다. 높이 1의 점프대가 있는 2번 칸의 답은 한 칸을 건너뛴 4번 칸의 답에 1을 더한 값이다. 다른 칸도 같은 방식으로 구한다. 8번 칸과 9번 칸은 각각 8번 칸, 9번 칸만 밟고 도로를 벗어나므로 답이 모두 1이다.

첫 번째 줄에 도로의 길이 $N$이 주어진다.

두 번째 줄에 1번 칸부터 $N$번 칸까지 순서대로 각 칸에 설치된 점프대의 높이가 공백으로 구분되어 주어진다. 점프대가 없는 칸은 0이 주어진다.

1번 칸부터 $N$번 칸까지 순서대로, 각 칸에서 자전거를 타고 앞으로 달리면 총 몇 개의 칸을 밟게 되는지 출력한다. 각 출력은 공백으로 구분한다.

• $1 \le N \le 200,000$
• $1 \le$ 점프대의 높이 $\le 200,000$