Cow Gift Queue

Farmer John's nemesis, Farmer Nhoj, has N cows (numbered from 1 to \(N\), where \(1 \le N \le 10^5\)). They have unexpectedly shown up at Farmer John's farm and queued up to receive gifts. Initially the cows are in order 1, 2, \(\dots\), N. Farmer John, having an infinite supply of gifts, begins distributing gifts from the front of the queue.

When a cow \(i\) at the head of the queue receives a gift, she does not simply go to the tail. Instead she cuts exactly \(c_i\) cows (with \(0 \le c_i \le N-1\)) at the tail of the queue and inserts herself so that exactly \(c_i\) cows are behind her. In other words, after receiving her gift and being removed from the head, cow \(i\) will reinsert herself into the queue at position \(N - c_i\) (when positions are numbered from 1 at the head to \(N\) at the tail).

Note that some cows may receive gifts multiple times, but Farmer John is worried that some cows might never receive a gift, no matter how many gifts are handed out. Your task is to determine the number of cows that never receive any gifts.

Hint: There is a neat solution using a stack-like greedy algorithm which processes the cows in reverse order.

inputFormat

The first line contains one integer \(N\) (the number of cows). The next line contains \(N\) integers \(c_1, c_2, \dots, c_N\) where \(0 \le c_i \le N-1\) for each cow \(i\). The cows are given in the order from the head to the tail of the initial queue.

outputFormat

Output a single integer, the number of cows that never receive any gifts, regardless of how many gifts are given out.

sample

3
2 0 0

2