题目描述

$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$

输出格式

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

题目大意

我们有 $n$ 堆煎饼，第 $i$ 堆的大小为 $a_i$。现在你需要进行下列操作一次（也可以不进行）：

• 选择两个整数 $l,r(1 ≤ l < r ≤ n)$ 并且翻转 $l$ 堆到第 $r$ 堆之间的煎饼的顺序。

比如 $a = [1,2,3,4,5]$，你可以选择操作 $[3,5]$，操作后序列变成 $[1,2,5,4,3]$。

找到操作后（或不操作）的序列可能的最小价值。一个煎饼堆的价值定义为 $|a_1 − a_2| + |a_2 − a_3 | + ... + |a_{n−1} − a_n |$。

5
7 14 12 2 6

17

3
111 119 999

888

6
12 15 3 4 15 7

19

7
100 800 500 400 900 300 700

1800

10
535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725

2576376600

提示

制約

• $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$ となります。