Maximum Difference over All Substrings

Problem Description

The maximum difference of a sequence is defined as the difference between its maximum and minimum elements. For example, the maximum difference of $(3, 1, 4, 5, 6)$ is $6 - 1 = 5$, and that of $(2, 2)$ is $2 - 2 = 0$.

A substring of a sequence is a contiguous segment of it.

Given an array $a_1, a_2, \dots, a_n$ of length $n$, compute the sum of the maximum differences over all substrings of the sequence.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output one line containing a single integer: the answer.

Sample Input

3
1 2 3

Sample Output

4

Constraints

$1 \le n \le 500000$, $0 \le a_i \le 10^8$.