Bicycle Stunts

A straight bicycle road is $N$ meters long. The road is divided into $N$ cells of 1 meter each, numbered 1, 2, …, $N$ from the leftmost cell.

Each cell may have a jump ramp. Let $h_i$ be the height of the ramp in cell $i$. When a rider steps on a ramp of height $h_i$, the rider flies over the next $h_i$ cells regardless of any other factor and lands on the cell after them. Look at this example.

Starting from cell 1 and riding forward, the following happens in order.

1. Cell 1 has no ramp, so the rider moves to cell 2.
2. Cell 2 has a ramp of height 1, so the rider flies over cell 3 and lands on cell 4.
3. Cell 4 has a ramp of height 2, so the rider flies over cells 5 and 6 and lands on cell 7.
4. Cell 7 has no ramp, so the rider moves to cell 8.
5. Cell 8 has a ramp of height 3, so the rider flies over cell 9 and goes far ahead. (If the road were long enough, the rider would have landed on the imaginary cell 12.)

Sieun wants to know how many cells the rider steps on when riding forward from each starting cell. Testing all $N$ cells one by one is tedious. Sieun built the table below and noticed that the answer for a cell can be computed from the answer for a cell to its right.

Cell 1 has no ramp, so its answer is the answer for cell 2 plus 1. Cell 2 has a ramp of height 1, so its answer is the answer for cell 4 plus 1, skipping one cell. The other cells work the same way. Cells 8 and 9 have answer 1, since the rider steps on only cell 8 and only cell 9, respectively, and then leaves the road.

The first line contains $N$, the length of the road.

The second line contains the ramp heights for cells 1 through $N$, in order, separated by spaces. A cell with no ramp is given as 0.

For cells 1 through $N$, in order, print the number of cells the rider steps on when starting from that cell and riding forward. Separate the numbers with spaces.

• $1 \le N \le 200,000$
• $1 \le$ ramp height $\le 200,000$