[DTCPC 2024] 序列

定义一个长度为 $n$ 的序列 $\{p_n\}$ 的权值 $f(\{p_n\})$ 为 $\max\limits_{i=1}^n\{p_i-\max\{p_{i-1},p_{i+1}\}\}$，特别的，定义 $p_0=p_{n+1}=-\inf$。 求 $\sum\limits_{l=1}^n \sum\limits_{r=l+1}^n f(\{a_l,a_{l+1},\dots,a_r\})$。 答案对 $2^{32}$ 取模。

第一行一个正整数 $n$（$1 \le n \le 10^6$）。 第二行 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）。

一行一个数表示答案。 答案对 $2^{32}$ 取模。

5
1 3 5 2 3

21

4
4 6 3 3

12