配点: $800$ 点

問題文

$N$ 枚のパンケーキが積み重なった「パンケーキタワー」があります。最初、上から $i$ 番目 $(1 \leq i \leq N)$ のパンケーキの大きさは $A_i$ です。シェフである高橋君は、このパンケーキタワーに対して次の操作を最大 $1$ 回行うことができます。

• 整数 $l, r$ $(1 \leq l \lt r \leq N)$ を選び、上から $l, l+1, \dots, r$ 番目のパンケーキの並び方を反転させる。

ここで、見栄えの悪さを次のように定義するとき、操作後の見栄えの悪さとして考えられる最小の値を求めてください。

隣り合うパンケーキの大きさの差の総和。 すなわち、上から $i$ 番目のパンケーキの大きさを $A^{\prime}_i$ とするときの、$|A^{\prime}_1 - A^{\prime}_2| + |A^{\prime}_2 - A^{\prime}_3| + \cdots + |A^{\prime}_{N-1} - A^{\prime}_N|$ の値。

制約

• $2 \leq N \leq 300000$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数

入力

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

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

出力

見栄えの悪さとして考えられる最小の値を出力してください。

5
7 14 12 2 6

17

$l = 2, r = 5$ を選んで操作をすると、操作後のパンケーキの大きさは上から順に $7, 6, 2, 12, 14$ となります。

このときの見栄えの悪さは $|7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17$ です。これが最小値となり、他のどんな方法を使ってもこれより見栄えの悪さを小さくすることはできません。

3
111 119 999

888

この入力例では、操作をしないことで見栄えの悪さを最小にすることができます。

このとき、パンケーキの大きさは上から順に $111, 119, 999$ となり、見栄えの悪さは $|111-119| + |119-999| = 8 + 880 = 888$ となります。

6
12 15 3 4 15 7

19

$l = 3, r = 5$ を選んで操作をすると、操作後のパンケーキの大きさは上から順に $12, 15, 15, 4, 3, 7$ となります。

このときの見栄えの悪さは $|12-15| + |15-15| + |15-4| + |4-3| + |3-7| = 3 + 0 + 11 + 1 + 4 = 19$ で、これが最小値となります。

7
100 800 500 400 900 300 700

1800

$l = 2, r = 4$ を選んで操作をすると、操作後のパンケーキの大きさは上から順に $100, 400, 500, 800, 900, 300, 700$ となり、このときの見栄えの悪さは $1800$ となります。

10
535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725

2576376600