Subarray Weight Sum

Given a sequence \(a_1, a_2, \ldots, a_n\), compute the value of

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

In other words, for every contiguous subarray, define its weight as the difference between its maximum and minimum element, and output the sum of weights for all contiguous subarrays.

inputFormat

The first line contains a single integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\).

outputFormat

Output a single integer, the sum of weights of all contiguous subarrays.

sample

3
1 2 3

4