← 返回题目列表

AtCoder · tkppc4_1_k

K. 天使和作业

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

配点: 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