Mirko discovered what Slavko did in the previous task, and decided to deal with something completely different from tables of letters: sequences of numbers.

Let's define a value of a sequence as the difference between the largest and the smallest number within that sequence. For example, value of sequence $(3,1,7,2)$ is $6$, and value of $(42,42)$ is $0$.

Find the sum of values of all subsequences of consecutive elements of a given sequence.

Input Specification

The first line of input contains a single integer $N$ $(2\le N\le 300000)$, number of elements of the sequence. Next $N$ lines contain elements of the sequence. Each element is a positive integer not greater than $100000000$.

Output Specification

The first and only line of output must contain the requested sum.

Sample Input 1

3
1
2
3

Sample Output 1

4

Sample Input 2

4
7
5
7
5

Sample Output 2

12

Sample Input 3

4
3
1
7
2

Sample Output 3

31