SP22343 NORMA2 - Norma

你有一个长度为 $n$ 的序列，定义这个序列中每个区间的价值是 $Cost(l,r) = \max(a_l,a_{l+1}, \dots, a_r) \times \min(a_l,a_{l+1}, \dots, a_r) \times (r - l + 1)$ 其中，$l$，$r$ 是区间的两个端点。 现在请你求出给定序列所有区间的价值之和对 $10^9$ 取模的结果。

第 $1$ 行一个整数 $n$，表示这个序列有 $n$ 个数。 第 $2$ ~ $n+1$ 行每行一个整数，第 $i+1$ 行的整数代表这个序列的第 $i$ 个数。

一行，一个整数。给定序列所有区间的价值之和对 $10^9$ 取模的结果。

## 样例输入（与原题的样例不同） ``` 4 2 4 1 4 ``` ## 样例输出 ``` 109 ``` ## 数据范围 对于所有数据保证 $n \le 5 \times 10^5$，所有序列中的数 $A_i$ 满足 $A_{i} \le 10^8$。