题目描述
给定一个整数数列 $a_1,a_2,\cdots,a_n$，请计算：
$$s=\sum_{1\leq i\leq j\leq n}\Big\{(j-i+1)\times\min[i,j]\times\max[i,j] \Big\}$$
其中 $\min[i,j]$ 表示 $a_i$ 到 $a_j$ 的最小值，$\max[i,j]$表示 $a_i$ 到 $a_j$ 的最大值，由于数字很大，取结果模 $10^9+7$ 的余数。
输入
第一行：单个整数 $n$ 表示数列的长度。
第二行：$n$ 个整数，表示 $a_1$ 到 $a_n$。
输出
单个整数：表示 $s$ 模 $10^9+7$ 的余数。
样例输入输出
提示
+ 对于 $30\%$ 的数据，满足 $n \leq 200$；
+ 对于 $60\%$ 的数据，满足 $n \leq 10000$；
+ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 500000$，$1\leq a_i\le 10^9$
样例1说明:
$25 = 1*1*1 + 1*4*4 + 2*1*4 $