P6406 [COCI 2014/2015 #2] Norma

Given a positive integer sequence $a_1,a_2,\cdots,a_n$, compute $$\sum_{i=1}^{n}\sum_{j=i}^{n}(j-i+1)\min(a_i,a_{i+1},\cdots,a_j)\max(a_i,a_{i+1},\cdots,a_j)$$

The first line contains an integer $n$. The next $n$ lines each contain a positive integer, representing the input sequence $a_1,a_2,\cdots,a_n$.

Output the result modulo $10^9$.

For $100\%$ of the testdata, $1 \le n \leq 5\times 10^5$, $1 \le a_i \le 10^8$. Translated by ChatGPT 5