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 \leq N \leq 300\,000)~, number of elements of the sequence. Next ~N~ lines contain elements of the sequence. Each element is a positive integer not greater than ~100\,000\,000~.

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