問題文

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

整数列 $B = (B_1, \\ldots, B_N)$ および $C = (C_1, \\ldots, C_N)$ の組であって、以下の条件を満たすものを考えます：

• $1\\leq i\\leq N$ に対して $A_i = B_i + C_i$ が成り立つ。
• $B$ は広義単調増加である。つまり $1\\leq i\\leq N-1$ に対して $B_i\\leq B_{i+1}$ が成り立つ。
• $C$ は広義単調減少である。つまり $1\\leq i\\leq N-1$ に対して $C_i\\geq C_{i+1}$ が成り立つ。

$\\sum_{i=1}^N \\bigl(\\lvert B_i\\rvert + \\lvert C_i\\rvert\\bigr)$ としてありうる最小値を求めてください。

制約

• $1\\leq N\\leq 2\\times 10^5$
• $\-10^8\\leq A_i\\leq 10^8$

入力

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

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

出力

答えを出力してください。

入力例 1

3
1 -2 3

出力例 1

10

最小値を与える整数列 $B$, $C$ として、例えば次があります：

• $B = (0, 0, 5)$
• $C = (1, -2, -2)$

$\\sum_{i=1}^N \\bigl(\\lvert B_i\\rvert + \\lvert C_i\\rvert\\bigr) = (0+1) + (0+2) + (5+2) = 10$ となっています。

入力例 2

4
5 4 3 5

出力例 2

17

最小値を与える整数列 $B$, $C$ として、例えば次があります：

• $B = (0, 1, 2, 4)$
• $C = (5, 3, 1, 1)$

入力例 3

1
-10

出力例 3

10

最小値を与える整数列 $B$, $C$ として、例えば次があります：

• $B = (-3)$
• $C = (-7)$