問題文

ミクシィ社員の青木さんは $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$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ $...$ $a_N$

出力

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

入力例 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