Description

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)$$

Input Format

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 Format

Output the result modulo $10^9$.

4
2
4
1
4

109

Hint

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

Translated by ChatGPT 5