問題文

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 を加算する。

なぷか君が目標を達成するのに必要な魔法をかける回数としてあり得る最小値を求めてください。

制約

• 2 \le N \le 100
• 0 \le D_i \le 1000

入力例 1

4
2 3 1

出力例 1

4

始め、(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 を選んでもよいことに注意してください。

入力例 2

3
0 0

出力例 2

0

入力例 3

10
1 9 5 6 2 7 1 4 8

出力例 3

22