問題文

長さ $N$ の整数列 $A=(A_1,A_2,\\ldots,A_N)$ が与えられます。

高橋君は次の $2$ 種類の操作のうち $1$ つを選んで行う事を、何回でも ($0$ 回でも良い) 繰り返し行う事ができます。

• $1\\leq i\\leq N-1$ をみたす整数 $i$ を選び、$A_i$ を $1$ 減らし、$A_{i+1}$ を $1$ 増やす。
• $1\\leq i\\leq N-1$ をみたす整数 $i$ を選び、$A_i$ を $1$ 増やし、$A_{i+1}$ を $1$ 減らす。

数列 $A$ が次の条件をみたすようにするために必要な操作の回数の最小値を求めてください。

• 任意の $1$ 以上 $N$ 以下の整数の組 $(i,j)$ に対して、$\\lvert A_i-A_j\\rvert\\leq 1$ が成り立つ。

制約

• $2 \\leq N \\leq 5000$
• $\\lvert A_i \\rvert \\leq 10^9$
• 入力はすべて整数

入力

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

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$

出力

数列 $A$ が問題文の条件をみたすようにするために必要な操作の回数の最小値を一行に出力せよ。

入力例 1

3
2 7 6

出力例 1

4

次のようにして $4$ 回の操作で $A$ が条件をみたすようにできます。

• $i=1$ を選び、$A_1$ を $1$ 増やし、 $A_2$ を $1$ 減らす。$A=(3,6,6)$ となる。
• $i=1$ を選び、$A_1$ を $1$ 増やし、 $A_2$ を $1$ 減らす。$A=(4,5,6)$ となる。
• $i=2$ を選び、$A_2$ を $1$ 増やし、 $A_3$ を $1$ 減らす。$A=(4,6,5)$ となる。
• $i=1$ を選び、$A_1$ を $1$ 増やし、 $A_2$ を $1$ 減らす。$A=(5,5,5)$ となる。

この時操作回数が最小であり、よって $4$ を出力します。

入力例 2

3
-2 -5 -2

出力例 2

2

次のようにして $2$ 回の操作で $A$ が条件をみたすようにできます。

• $i=1$ を選び、$A_1$ を $1$ 減らし、 $A_2$ を $1$ 増やす。$A=(-3,-4,-2)$ となる。
• $i=2$ を選び、$A_2$ を $1$ 増やし、 $A_3$ を $1$ 減らす。$A=(-3,-3,-3)$ となる。

この時操作回数が最小であり、よって $2$ を出力します。

入力例 3

5
1 1 1 1 -7

出力例 3

13

うまく操作することで、$13$ 回の操作の後で、 $A=(0,0,-1,-1,-1)$ にでき、これは問題文の条件をみたします。 $12$ 回以下の操作で条件をみたすようにすることはできないため、$13$ を出力します。