Problem Description

Define the weight \( f(\{p_n\}) \) of a sequence \(\{p_n\}\) of length \( n \) as \( \max\limits_{i=1}^n\{p_i-\max\{p_{i-1},p_{i+1}\}\}\), with the special definition \( p_0=p_{n+1}=-\infty \).

Calculate \( \sum\limits_{l=1}^n \sum\limits_{r=l+1}^n f(\{a_l,a_{l+1},\dots,a_r\}) \).

The answer should be taken modulo \( 2^{32} \).

Input Format

The first line contains a positive integer \( n \) (\( 1 \le n \le 10^6 \)).

The second line contains \( n \) integers \( a_i \) (\( 1 \le a_i \le 10^9 \)).

Output Format

Output a single number representing the answer.

The answer should be taken modulo \( 2^{32} \).

Sample Input and Output

Sample Input #1

5
1 3 5 2 3

Sample Output #1

21

Sample Input #2

4
4 6 3 3

Sample Output #2

12

见题面 Input 部分

见题面 Output 部分