Maximum Weight Partition

Problem Description

For a segment (contiguous subsequence) of a sequence, define its weight as the range of that segment, i.e. the difference between its maximum and minimum.

Given a sequence $a$, you may partition it into any number of consecutive segments. Find the maximum possible value of the sum of the weights of all segments.

Input Format

The first line contains an integer $n$, the length of the sequence ($1 \le n \le 10^6$).

The second line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$, the given sequence ($-10^9 \le a_i \le 10^9$).

Output Format

Output one line containing one integer: the maximum possible sum of the segment weights.

Sample Input

5
9 6 1 8 8

Sample Output

10

Sample Explanation

Partitioning as $[9,6], [1,8,8]$ gives the maximum weight.