Description

Given a sequence $a_i$ of length $n$, find the value of the following expression:

$$\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)$$

That is, define the weight of a subarray as the difference between the maximum and the minimum value within it. Find the sum of the weights of all contiguous subarrays.

Input Format

The first line contains an integer $n$, the length of the sequence.

The next $n$ lines each contain an integer $a_i$, describing the sequence.

Output Format

Output one integer in one line, representing the answer to the expression.

3
1
2
3

4

4
7
5
7
5

12

4
3
1
7
2

31

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $2\le n\le 3\times 10^5$ and $1\le a_i\le 10^8$.

Notes

Translated from COCI2010-2011 CONTEST #3 T5 DIFERENCIJA。

Translated by ChatGPT 5