Greedy Gift Takers

Time limit2sMemory limit512 MB

Summary

Each cow takes a gift and reinserts herself c_i positions from the tail; count how many cows never reach the head.

Level: Hard8 of 10
Topics: Math, Simulation
Solved: No attempts yet

Problem

Farmer John's rival, Farmer Nhoj, keeps $N$ cows ( $1 \leq N \leq 10^5$ ) numbered $1$ through $N$ . They have turned up at Farmer John's farm without warning, and Farmer John, always polite, decides to hand each of them a gift.

Farmer John has an unlimited supply of gifts. Nhoj's cows line up in front of him, cow $1$ at the head of the line and cow $N$ at the tail. Farmer John expected that at every timestep the cow at the head would take a gift and walk to the tail. Nhoj's cows are not that polite. After taking her gift, a cow does not go to the tail: she cuts in front of some of the cows near the tail. To be exact, cow $i$ always cuts exactly $c_i$ cows ( $0 \leq c_i \leq N-1$ ). The line always holds $N$ cows, so right after taking a gift cow $i$ stands at position $N - c_i$ counted from the head.

Since the supply is unlimited, Farmer John does not mind that some cows take several gifts. He does worry that some cows may take none at all.

Find how many cows never receive a gift, no matter how long the gifts are handed out.

Input

The first line contains one integer $N$ .

The second line contains the integers $c_1, c_2, \dots, c_N$ separated by spaces.

Output

Print the number of cows that never receive a gift.

Examples1

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