题目描述

定义一个长度为 $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