Problem Description

Given a sequence \( a_i \) of length \( n \), calculate the value of the following expression:

\[ \sum_{i=1}^{n} \sum_{j=i}^{n} \left( \max_{i \le k \le j} a_k - \min_{i \le k \le j} a_k \right) \]

This means the weight of a subsequence is defined as the difference between its maximum and minimum values. Find the sum of the weights of all continuous subsequences.

Input Format

The first line contains an integer \( n \), representing the length of the sequence.

The next \( n \) lines each contain an integer \( a_i \), describing the sequence.

Output Format

Output a single integer, which is the answer to the expression.

Sample Input and Output

Sample Input #1

3
1
2
3

Sample Output #1

4

Sample Input #2

4
7
5
7
5

Sample Output #2

12

Sample Input #3

4
3
1
7
2

Sample Output #3

31

Notes

Data Size and Constraints

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

Note

This problem is translated from COCI2010-2011 CONTEST #3 T5 DIFERENCIJA.

见题面 Input 部分

见题面 Output 部分