Subarray Weight Sum

Given an array a of length n, define the weight of a sequence p of length k as:

$f(\{p\}) = \max_{1 \le i \le k} \Big\{ p_i - \max\{ p_{i-1},\,p_{i+1} \} \Big\}$,

with the convention that
$p_0 = p_{k+1} = -\infty$.

For every contiguous subarray of a with length at least 2, compute its weight as defined above, and then output the sum over all these subarrays modulo $2^{32}$.

Note: In a subarray a[l...r], the indices are reinterpreted so that the first element has index 1 and the last has index r-l+1. Thus, the endpoints are handled with a single neighbor: for the first element, the calculation is a[l] - a[l+1], and for the last element, it is a[r] - a[r-1].

inputFormat

The first line contains a single integer n representing the number of elements in the array.

The second line contains n space-separated integers, which are the elements of the array a.

outputFormat

Output a single integer, which is the sum of the weights of all contiguous subarrays (of length at least 2) of the array a, taken modulo $2^{32}$.

sample

3
1 2 3

3