問題文

天使の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

入力例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 日目に訪れれば良いです。