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}\}\}$. In particular, define $p_0=p_{n+1}=-\inf$.

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

The answer is 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 one number representing the answer.

The answer is taken modulo $2^{32}$.

5
1 3 5 2 3

21

4
4 6 3 3

12

Hint

Translated by ChatGPT 5