AT_bcu30_2019_b Interval Addition

[problemUrl]: https://atcoder.jp/contests/bcu30-2019/tasks/bcu30_2019_b ミクシィ社員の青木さんは $ N $ 要素から成る数列 $ A $ を持っており、はじめ数列の全ての要素は $ 0 $ です。 青木さんは以下の操作を $ 0 $ 回以上繰り返して、全ての $ 1\ \leq\ i\ \leq\ N $ について数列の $ i $ 番目の要素が $ a_i $ になるようにしたいです。 - $ 1\ \leq\ k\ \leq\ N $ と $ 1\ \leq\ l\ \leq\ N+1-k $ を満たす正の整数 $ k,\ l $ を決める。長さ $ k $ の非負整数列 $ (0\ \leq\ )B_1 \leq\ B_2\ \leq\ ...\ \leq\ B_k $ を好きに決め、$ 1\ \leq\ i\ \leq\ k $ に対して $ A_{l+i-1}\ :=\ A_{l+i-1}\ +\ B_i $ とする。 毎回の操作では異なる $ k,\ l,\ B $ を使うことができます。青木さんが目的の数列を得るために、最小で何回の操作が必要となるかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

青木さんが目的の数列を得るために必要な操作回数の最小値を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ a_i\ \leq\ 10^9 $ - 入力は全て整数である ### Sample Explanation 1 $ k\ =\ 2,\ l\ =\ 1,\ B\ =\ \{3,\ 4\} $ とすると、 青木さんは $ 1 $ 回の操作で目的の数列を得ることができます。 ### Sample Explanation 2 $ 1 $ 回目の操作で $ k\ =\ 2,\ l\ =\ 1,\ B\ =\ \{3,\ 3\} $ とすると $ A $ は $ \{3,\ 3\} $ となります。 $ 2 $ 回目の操作で $ k\ =\ 1,\ l\ =\ 1,\ B\ =\ \{1\} $ とすると $ A $ は $ \{4,\ 3\} $ となります。 よって青木さんは $ 2 $ 回の操作で目的の数列を得ることができ、また $ 1 $ 回以下で目的の数列を得ることは出来ないので $ 2 $ を出力してください。