题目描述

有 $N$ 张煎饼叠成了一座“煎饼塔”。最初，从上往下第 $i$ 张煎饼的大小为 $A_i$。作为厨师的高桥君可以对这座煎饼塔最多进行 $1$ 次如下操作：

• 选择整数 $l,\ r$，满足 $1 \leq l < r \leq N$，将从上往下第 $l,\ l+1,\ \dots,\ r$ 张煎饼的顺序反转。

这里，难看的程度定义如下，请你求出操作后可能得到的最小难看程度。

相邻两张煎饼大小之差的绝对值之和。
也就是说，若操作后从上往下第 $i$ 张煎饼的大小为 $A'_i$，则难看程度为 $|A'\_1 - A'\_2| + |A'\_2 - A'\_3| + \cdots + |A'\_{N-1} - A'\_N|$。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

输出操作后可能得到的最小难看程度。

样例 1

输入

5
7 14 12 2 6

输出

17

样例 2

输入

3
111 119 999

输出

888

样例 3

输入

6
12 15 3 4 15 7

输出

19

样例 4

输入

7
100 800 500 400 900 300 700

输出

1800

样例 5

输入

10
535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725

输出

2576376600

说明/提示

限制条件

• $2 \leq N \leq 300000$
• $1 \leq A_i \leq 10^9$
• 所有输入均为整数

样例解释 1

选择 $l = 2,\ r = 5$ 进行操作后，煎饼的大小依次为 $7,\ 6,\ 2,\ 12,\ 14$。此时的难看程度为 $|7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17$。这是最小值，无论采用其他方式都无法使难看程度更小。

样例解释 2

对于本输入样例，不进行操作即可使难看程度最小。此时煎饼的大小依次为 $111,\ 119,\ 999$，难看程度为 $|111-119| + |119-999| = 8 + 880 = 888$。

样例解释 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$，这是最小值。

样例解释 4

选择 $l = 2,\ r = 4$ 进行操作后，煎饼的大小依次为 $100,\ 400,\ 500,\ 800,\ 900,\ 300,\ 700$，此时难看程度为 $1800$。

由 ChatGPT 4.1 翻译