問題文

ミクシィ社員の青木さんは 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 を使うことができます。青木さんが目的の数列を得るために、最小で何回の操作が必要となるかを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9
• 入力は全て整数である

入力例 1

2
3 4

出力例 1

1

k = 2, l = 1, B = \{3, 4\} とすると、 青木さんは 1 回の操作で目的の数列を得ることができます。

入力例 2

2
4 3

出力例 2

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 を出力してください。

入力例 3

4
4 0 4 0

出力例 3

2