Greedy Gift Takers#10520
Farmer John's nemesis, Farmer Nhoj, has cows, conveniently numbered . They have unexpectedly arrived at Farmer John's farm, so the unfailingly polite Farmer John is attempting to give them gifts.
To do so, Farmer John has brought out his infinite supply of gifts, and Nhoj's cows have lined up in front of him, with cow at the front of the queue and cow at the back. Farmer John expected that at each timestep, the cow at the front of the queue would take a gift from Farmer John and move to the back of the queue. However, he has just realized that Nhoj's cows are not quite so polite! After receiving her gift, a cow may choose not to move to the back of the queue. Instead, she may cut in front of some number of cows at the back of the queue. Specifically, cow will always cut in front of exactly c_i cows.
Farmer John knows that some cows may receive multiple gifts; since he has an infinite supply, this does not concern him. However, he is worried that some cows might become unhappy if they never receive a gift.
Help Farmer John determine the number of cows that never receive a gift, no matter how many gifts are handed out.
The first line contains one integer n~(1 \le n \le 10^5). The second line contains integers c_1, c_2, \ldots, c_n~(0 \le c_i \le n - 1).
Print the number of cows that can never receive a gift.
Example 1