配点: 500 点
問題文
天使G先生和恶魔V先生在人类世界上高中。
今天我们两个人被布置了暑假作业!暑假是 N 作业是
有一个 N 页面。
魔王V先生是个计划者,所以他每天都会做作业。 1 我决定一页一页地做。
然而,天使G先生忙着给人间带来祝福,根本没有时间做作业!
于是,我决定请V老师抄写他的作业。
i 当天G先生拜访V先生时,V先生的心情是 a_i 最多在那一天。 a_i 您可以复印几页作业。
天使G先生很忙,所以他尽量不想去看望V先生。为了完成作业,G 先生最少需要拜访 V 先生多少次?
但是,
运算前设定中包含的i 当G先生第一天拜访V先生时,V先生已经完成了作业。 i 假设您已完成页码。
此外,i 当天的作业 i+1 请注意,您将无法在该页之外复印任何内容。
此外,G 先生同一天不能多次拜访 V 先生。
制約
- 所有输入均为整数。
- 1\leq N\leq2\times10^5
- 1\leq a_i\leq 10^9
入力
输入是按以下格式从标准输入给出的。
N
a_1 a_2 \ldots a_{N-1} a_N
出力
请将G先生拜访V先生的最少次数输出到标准输出。
入力例1
5
1 1 3 2 2
出力例1
2
3 日和 5 日访问。 最好在
入力例2
6
1 1 2 1 1 2
出力例2
4
例如,1 日目、3 日目、4 日目、6 日访问。 最好在
入力例3
8
1 1 2 1 2 3 1 3
出力例3
3
例如 第 3 日目、6 日目、8 日参观。
作者: TMJN