幽谷传响

题目描述

Orange进入了一片连绵的山脉，这片山脉由 $n$ 座山峰组成，第 $i$ 座山峰的海拔为 $a_i$ 。

Orange定义一处幽谷：对于一片连续的山脉 $[a_i, a_{i + 1} ... a_{i + k}]$ ，其幽谷为其中海拔最低的山峰。

现在，Orange想求出这片山脉中所有的幽谷的海拔之和，请你帮助他完成这件事。由于答案可能很大，请你输出答案对 $10^9+7$ 取 $\bmod$ 的值。

形式化的说，你应该求出如下函数的值：

$$F = \sum_{i = 1}^n \sum_{j = i}^n \min_{k = i} ^ j a_k \pmod{10^9+7}$$

输入共 2 行：第一行为一个整数 $n$ ，表示山峰的数量。第二行为 $n$ 个整数 $a_i$ ，表示各个山峰的海拔。

$1 \le n \le 10^6$ $1 \le a_i \le 10^6$

输出一个整数表示答案。

4
3 1 2 4