题目描述

给定一个整数数列 $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$ 的余数。

2
1 4

25

样例解释 1

25 = 111 + 144 + 214

4
1 2 3 4

119

数据范围

• 对于 $30\%$ 的数据，满足 $n \leq 200$；
• 对于 $60\%$ 的数据，满足 $n \leq 10000$；
• 对于 $100\%$ 的数据，满足 $1 \leq n \leq 500000$，$-10^9\leq a_i\le 10^9$