Problem Description

Unagi received a sequence $A = \{A_1, A_2, ..., A_N\}$ from Santa Rabbit for Christmas.

Unagi decided to create a "good sequence" by removing some (possibly zero) elements from sequence $ A $. A sequence $ x $ is considered good if it satisfies the following properties:

• For all $i\ (2 ≦ i ≦ |x|-1)$, $ x_i $ is not the median of $ x_{i-1}, x_i, x_{i+1} $.

For example, $x = \{2, 1, 3, 2\}$ and $x = \{2, 1, 2\}$ satisfy the condition, but $x = \{1, 2, 3\}$ and $x = \{1, 1, 3, 2\}$ do not. Sequences with a length less than 3 also satisfy the condition.

The ruggedness of a sequence $ x $ is defined as the sum of the differences between adjacent numbers. In mathematical terms, it is expressed as $ Σ_{1 ≦ i ≦ |x|-1} |x_i - x_{i+1}| $.

Find the maximum ruggedness of a good sequence that can be created.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $

• The first line contains an integer $N\ (2 ≦ N ≦ 10^5)$, representing the length of sequence $ A $.
• The second line contains $ N $ integers separated by spaces. The $ i $-th integer $A_i\ (0 ≦ A_i ≦ 10^9)$ is given.

Output Format

Output the maximum ruggedness of a good sequence that can be obtained by removing some elements from sequence $ A $. End the output with a newline.

Sample Input and Output

Sample Input #1

5
1 1 3 2 1

Sample Output #1

4

Sample Input #2

7
2 1000000000 0 1000000000 1 1000000000 5

Sample Output #2

5999999991

Notes/Hints

Partial Points

This problem has partial points:

• If you solve the dataset where $ N ≦ 1,000 $, you will be awarded 20 points.
• If you solve the dataset without additional constraints, you will be awarded an additional 80 points.

Sample Explanation 1

For example, removing the 1st and 4th elements results in $\{1, 3, 1\}$, with a ruggedness value of 4.

见题面 Input 部分

见题面 Output 部分