AT_abc480_g [ABC480G] Zonal Score Minimization

長さ $ 2 $ 以上の正整数列のスコアをその数列の最大値と最小値の差で定義します。 長さ $ N $ の正整数列 $ A $ が与えられるので、 $ A $ を長さ $ 2 $ 以上であるような $ 1 $ つ以上の連続部分列に分割したときに各連続部分列のスコアの総和としてあり得る値の最小値を求めてください。 より形式的には、ある正整数 $ K $ に対して長さが $ 2 $ 以上であるような $ K $ 個の正整数列 $ B_1,B_2,\dots,B_K $ をこの順に連結させると $ A $ と同じ数列になるときに $ \sum_{k=1}^{K}\left(\max(B_k)-\min(B_k)\right) $ としてあり得る値の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを $ 1 $ 行で出力せよ。

### Sample Explanation 1 $ A $ を $ (1,3) $ と $ (6,8,9) $ に分割すると、スコアはそれぞれ $ 2,3 $ となり、総和は $ 5 $ です。 各連続部分列のスコアの総和を $ 4 $ 以下にすることはできないため、答えは $ 5 $ です。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - 入力される値はすべて整数