AT_arc119_e [ARC119E] Pancakes

[problemUrl]: https://atcoder.jp/contests/arc119/tasks/arc119_e $ 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| $ の値。

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

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

### 制約 - $ 2\ \leq\ N\ \leq\ 300000 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 $ l\ =\ 2,\ r\ =\ 5 $ を選んで操作をすると、操作後のパンケーキの大きさは上から順に $ 7,\ 6,\ 2,\ 12,\ 14 $ となります。 このときの見栄えの悪さは $ |7-6|\ +\ |6-2|\ +\ |2-12|\ +\ |12-14|\ =\ 1\ +\ 4\ +\ 10\ +\ 2\ =\ 17 $ です。これが最小値となり、他のどんな方法を使ってもこれより見栄えの悪さを小さくすることはできません。 ### Sample Explanation 2 この入力例では、操作をしないことで見栄えの悪さを最小にすることができます。 このとき、パンケーキの大きさは上から順に $ 111,\ 119,\ 999 $ となり、見栄えの悪さは $ |111-119|\ +\ |119-999|\ =\ 8\ +\ 880\ =\ 888 $ となります。 ### Sample Explanation 3 $ 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 $ で、これが最小値となります。 ### Sample Explanation 4 $ l\ =\ 2,\ r\ =\ 4 $ を選んで操作をすると、操作後のパンケーキの大きさは上から順に $ 100,\ 400,\ 500,\ 800,\ 900,\ 300,\ 700 $ となり、このときの見栄えの悪さは $ 1800 $ となります。