Subarray Min-Max Weighted Sum

Given a sequence of positive integers \(a_1, a_2, \ldots, a_n\), calculate the following sum:

\[ S = \sum_{i=1}^{n} \sum_{j=i}^{n} (j-i+1) \cdot \min(a_i, a_{i+1}, \ldots, a_j) \cdot \max(a_i, a_{i+1}, \ldots, a_j) \]

For each contiguous subarray, compute the product of the subarray length, its minimum and maximum element, and sum up these products for all subarrays.

inputFormat

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

outputFormat

Output a single integer, the calculated sum \(S\).

sample

1
5

25