AT_npcapc_2024_k Peace with Magic

NPCA 国は横一列に並んだ $ N $ 個のマスからなり、左から順に $ 1 $ から $ N $ の番号がつけられています。ここで、マス $ i $ の高さを $ H_i $ とします。始め、 $ H_1=H_2=\dots=H_N=0 $ となっています。 各 $ 1\le i\le N-1 $ について、 $ H_i $ と $ H_{i+1} $ の差の絶対値が $ D_i $ 未満であるとき、マス $ i $ とマス $ i+1 $ の間で争いが起こってしまいます。さて、平和を愛する NPCA 国の王のなぷか君の目標はどの隣り合うマスの間でも争いが起きなくなることです。そのため、なぷか君は以下の魔法を $ 0 $ 回以上かけることが出来ます。 - $ H_i=H_{i+1}=\dots=H_{j} $ を満たす整数 $ i,j(1\le i\le j\le N) $ を選んで $ H_i,H_{i+1},\dots,H_{j} $ に $ 1 $ を加算する。 なぷか君が目標を達成するのに必要な魔法をかける回数としてあり得る最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D_1 $ $ D_2 $ $ \dots $ $ D_{N-1} $

答えを出力せよ。

### Sample Explanation 1 始め、 $ (H_1,H_2,H_3,H_4)=(0,0,0,0) $ です。例えば、次のように魔法をかけることができます。 - $ (i,j)=(1,3) $ とする。 $ (H_1,H_2,H_3,H_4)=(1,1,1,0) $ となる。 - $ (i,j)=(1,2) $ とする。 $ (H_1,H_2,H_3,H_4)=(2,2,1,0) $ となる。 - $ (i,j)=(2,2) $ とする。 $ (H_1,H_2,H_3,H_4)=(2,3,1,0) $ となる。 - $ (i,j)=(2,2) $ とする。 $ (H_1,H_2,H_3,H_4)=(2,4,1,0) $ となる。 目標を達成するまでに魔法を $ 4 $ 回かけており、これが最小です。 $ i=j $ となる $ i,j $ を選んでもよいことに注意してください。 ### Constraints - $ 2 \le N \le 100 $ - $ 0 \le D_i \le 1000 $