Alternating Min–Max Subarray Game

You are given an integer array a[1…N] of length N (with 2 ≤ N ≤ 106, and 1 ≤ a[i] ≤ N). For each non‐empty contiguous subarray of a (that is, every sequence a[l], a[l+1], …, a[r] with 1 ≤ l ≤ r ≤ N), consider the following game played on the subarray:

1. The game starts with the given list of integers. A series of operations is performed until only one number remains.
2. The operations alternate – the first operation is a min–operation and the second is a max–operation, the third is again a min–operation, and so on.
3. In each operation you are allowed to choose any two adjacent numbers and replace them with either their minimum (if it is a min–operation) or their maximum (if it is a max–operation).

You want to choose the order in which the operations are applied so that the final remaining number is maximized. Denote by f(S) the maximum final value achievable on list S when starting with a min–operation. (Note that if S contains only one element then f(S)=S[1] and if S has two elements then f(S)=min(S[1],S[2]).)

Your task is to compute the sum over all contiguous subarrays of a of f(subarray), and output that sum.

Note: The formal time‐limit for this problem is 3 seconds (which is typically 1.5 times the normal limit).

inputFormat

The first line contains a single integer N — the size of the array.

The second line contains N space‐separated integers, a[1], a[2], …, a[N].

outputFormat

Output a single integer — the sum of the answers f(S) over all contiguous subarrays S of a.

sample

3
4 10 3

28