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.