Sum of Sequence Values

Time limit1sMemory limit128 MB

Summary

Given an array, compute the sum over all contiguous subarrays of (max - min) efficiently for up to 300,000 elements.

Level: Medium6 of 10
Topics: Stack, Array, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
3
1
2
3
```
Expected output
```
4
```
Example 2
Input
```
4
7
5
7
5
```
Expected output
```
12
```
Example 3
Input
```
4
3
1
7
2
```
Expected output
```
31
```