/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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
出力
見栄えの悪さとして考えられる最小の値を出力してください。
入力例 1
5 7 14 12 2 6
出力例 1
17
l = 2, r = 5 を選んで操作をすると、操作後のパンケーキの大きさは上から順に 7, 6, 2, 12, 14 となります。
このときの見栄えの悪さは |7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17 です。これが最小値となり、他のどんな方法を使ってもこれより見栄えの悪さを小さくすることはできません。
入力例 2
3 111 119 999
出力例 2
888
この入力例では、操作をしないことで見栄えの悪さを最小にすることができます。
このとき、パンケーキの大きさは上から順に 111, 119, 999 となり、見栄えの悪さは |111-119| + |119-999| = 8 + 880 = 888 となります。
入力例 3
6 12 15 3 4 15 7
出力例 3
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 で、これが最小値となります。
入力例 4
7 100 800 500 400 900 300 700
出力例 4
1800
l = 2, r = 4 を選んで操作をすると、操作後のパンケーキの大きさは上から順に 100, 400, 500, 800, 900, 300, 700 となり、このときの見栄えの悪さは 1800 となります。
入力例 5
10 535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725
出力例 5
2576376600
Score: 800 points
Problem Statement
We have a pancake tower which is a pile of N pancakes. Initially, the i-th pancake from the top (1 \leq i \leq N) has a size of A_i. Takahashi, a chef, can do the following operation at most once.
- Choose integers l and r (1 \leq l \lt r \leq N) and turn the l-th through r-th pancakes upside down, reversing the order.
Find the minimum possible ugliness of the tower after the operation is done (or not), defined below:
the ugliness is the sum of the differences of the sizes of adjacent pancakes;
that is, the value |A^{\prime}_1 - A^{\prime}_2| + |A^{\prime}_2 - A^{\prime}_3| + \cdots + |A^{\prime}_{N-1} - A^{\prime}_N|, where A^{\prime}_i is the size of the i-th pancake from the top.
Constraints
- 2 \leq N \leq 300000
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the minimum possible ugliness of the tower.
Sample Input 1
5 7 14 12 2 6
Sample Output 1
17
If we do the operation choosing l = 2 and r = 5, the pancakes will have the sizes of 7, 6, 2, 12, 14 from top to bottom.
The ugliness here is |7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17. This is the minimum value possible; there is no way to achieve less ugliness.
Sample Input 2
3 111 119 999
Sample Output 2
888
In this sample, not doing the operation minimizes the ugliness.
In that case, the pancakes will have the sizes of 111, 119, 999 from top to bottom, for the ugliness of |111-119| + |119-999| = 8 + 880 = 888.
Sample Input 3
6 12 15 3 4 15 7
Sample Output 3
19
If we do the operation choosing l = 3 and r = 5, the pancakes will have the sizes of 12, 15, 15, 4, 3, 7 from top to bottom.
The ugliness here is |12-15| + |15-15| + |15-4| + |4-3| + |3-7| = 3 + 0 + 11 + 1 + 4 = 19, which is the minimum value possible.
Sample Input 4
7 100 800 500 400 900 300 700
Sample Output 4
1800
If we do the operation choosing l = 2 and r = 4, the pancakes will have the sizes of 100, 400, 500, 800, 900, 300, 700 from top to bottom, for the ugliness of 1800.
Sample Input 5
10 535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725
Sample Output 5
2576376600