P10162 [DTCPC 2024] Sequence

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}$.

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 one number representing the answer. The answer is taken modulo $2^{32}$.

Translated by ChatGPT 5