K - 天使と宿題 /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 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 日目に訪れれば良いです。

writer: TMJN