[USACO17DEC] Greedy Gift Takers P

题目描述

Farmer John's nemesis, Farmer Nhoj, has $N$ cows ($1 \leq N \leq 10^5$), conveniently numbered $1 \dots N$. They have unexpectedly turned up at Farmer John's farm, so the unfailingly polite Farmer John is attempting to give them gifts. To this end, Farmer John has brought out his infinite supply of gifts, and Nhoj's cows have queued up in front of him, with cow $1$ at the head of the queue and cow $N$ at the tail. Farmer John was expecting that at every timestep, the cow at the head of the queue would take a gift from Farmer John and go to the tail of the queue. However, he has just realized that Nhoj's cows are not that polite! After receiving her gift, each cow may not go to the tail of the queue, but rather may cut some number of cows at the tail, and insert herself in front of them. Specifically, cow $i$ will always cut exactly $c_i$ cows ($0 \leq c_i \leq N-1$). Farmer John knows that some cows might receive multiple gifts; as he has an infinite supply, this does not worry him. But he is worried that some cows might become unhappy if they do not get any gifts. Help Farmer John find the number of cows who never receive any gifts, no matter how many gifts are handed out. 有 N($1≤N≤10^5$)头牛按顺序排成一列,编号从 1 到 N,1 号牛在队头,N 号牛在队尾。 每次位于队头的牛 i 拿到一个礼物,然后插入到从队尾数$c_i$头牛之前的位置。。举个栗子: 初始队列 1,2,3,4,5 $c_1$ = 2,$c_2$ = 3,则第一次操作后的序列为 2,3,1,4,5,第二次操作后的序列为 3,2,1,4,5。重复无限次操作,求最后有几头牛拿不到礼物。

输入输出格式

输入格式


The first line contains a single integer, $N$. The second line contains $N$ space-separated integers $c_1, c_2, \dots, c_N$.

输出格式


Please output the number of cows who cannot receive any gifts.

输入输出样例

输入样例 #1

3
1 2 0

输出样例 #1

1