201194: [AtCoder]ARC119 E - Pancakes
Description
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