Greedy Gift Takers

题目描述

农夫 John 的死对头农夫 Nhoj 有 $N$ 头奶牛（$1 \leq N \leq 10^5$），方便起见编号为 $1 \dots N$。它们意外地出现在农夫 John 的农场里，因此一向彬彬有礼的农夫 John 正试图送给它们礼物。 为此，农夫 John 拿出了他无限的礼物供给，Nhoj 的奶牛在他面前排成一队，奶牛 $1$ 在队首，奶牛 $N$ 在队尾。农夫 John 原本以为在每一个时间步，队首的奶牛会从他那里拿一个礼物，然后走到队尾。然而，他刚刚意识到 Nhoj 的奶牛并没有那么有礼貌！每头奶牛在收到礼物后，可能不会走到队尾，而是会从队尾插队，越过队尾的一些奶牛，并插入到它们前面。具体来说，奶牛 $i$ 总是恰好越过 $c_i$ 头奶牛（$0 \leq c_i \leq N-1$）。 农夫 John 知道有些奶牛可能会收到多个礼物；由于他有无限的礼物供给，这并不会让他担心。但他担心有些奶牛如果一直拿不到礼物就会不开心。 请帮助农夫 John 求出：无论发出多少个礼物，永远收不到任何礼物的奶牛数量。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格分隔的整数 $c_1, c_2, \dots, c_N$。

输出格式

请输出无法收到任何礼物的奶牛数量。

3
1 2 0

1

提示

题目来源：Dhruv Rohatgi

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum