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

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

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

The first line of input contains a single integer \(N\) (\(2 \le N \le 300\,000\)), the number of elements of the sequence.

The next \(N\) lines contain the elements of the sequence. Each element is a positive integer not greater than \(100\,000\,000\).

The first and only line of output must contain the requested sum.
EXAMPLE TEST DATA
input

3
1
2
3

input

4
7
5
7
5
input

4
3
1
7
2
output

4
output

12
output

31

riseoj 작성

출처 COCI 2010/2011 Contest 3