← 返回题目列表

AtCoder · jag2017summer_day1_b

B. 松鼠

中文机器翻译题面 查看原题

問題文

一只蚱蜢和一只懒猴排队买圣诞蛋糕。

据正在观看的游客透露,目前已知以下信息。

  • 合計 N 动物们按顺序排列起来。
  • 队列中的所有动物要么是螽斯,要么是懒猴。 排队的第
  • i 只动物正是 A_i 您跳过了一些不按顺序排列的动物。
  • 慢懒猴从未超越慢懒猴。

现在,最多有多少只懒猴在排队?

制約

  • 1≦N≦300,000
  • 0≦A_i≦i-1

入力

输入将以以下形式从标准输入给出。

N
A_1 A_2 ... A_N

出力

打印矩阵中懒猴的最大可能数量。


入力例 1

3
0 0 1

出力例 1

2

通过此输入 只有第 3 只动物跳过了它的回合,2 进来的动物已通过。 因此,2 与动物 3 动物不可能是懒猴,而懒猴是 您可以看到少于 2 。 第

另外,1 与动物 2 个动物可能是懒猴,所以答案是 2 。


入力例 2

4
0 1 2 3

出力例 2

1

通过此输入,2 不可能有不止一只懒猴。


入力例 3

7
0 0 1 0 0 2 4

出力例 3

4