Sum of Sequence Values

The value of a sequence is the difference between its largest element and its smallest element.

For example, the value of (3, 1, 7, 2) is 7 - 1 = 6, and the value of (42, 42) is 42 - 42 = 0.

You are given a sequence of length N. For every contiguous subsequence of this sequence, compute its value, and output the sum of all those values.

For (3, 1, 7, 2), there are 10 contiguous subsequences: (3), (1), (7), (2), (3, 1), (1, 7), (7, 2), (3, 1, 7), (1, 7, 2), and (3, 1, 7, 2). The sum of their values is 31.

The first line contains the size of the sequence, N (2 <= N <= 300,000).

Each of the next N lines contains one element of the sequence. Every element is a positive integer not greater than 100,000,000.

Print one line containing the sum of the values of all contiguous subsequences of the given sequence.