Description

给定一个正整数序列 $a_1,a_2,\cdots,a_n$ ，求

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

第一行一个整数 $n$ 。
接下来 $n$ 行，每行一个正整数，表示输入序列 $a_1,a_2,\cdots,a_n$ 。

Output Format

输出答案对 $10^9$ 取模后的结果。

4
2
4
1
4

109

Hint

对于 $100\%$ 的数据，$1 \le n \leq 5\times 10^5$，$1 \le a_i \le 10^8$。