P6503 [COCI 2010/2011 #3] DIFERENCIJA

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.

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 one integer in one line, representing the answer to the expression.

#### 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](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T5 DIFERENCIJA***。 Translated by ChatGPT 5