CF1167F.Scalar Queries

You are given an array $a_1, a_2, \dots, a_n$. All $a_i$ are pairwise distinct.

Let's define function $f(l, r)$ as follows:

• let's define array $b_1, b_2, \dots, b_{r - l + 1}$, where $b_i = a_{l - 1 + i}$;
• sort array $b$ in increasing order;
• result of the function $f(l, r)$ is $\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$.

Calculate $\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$, i.e. total sum of $f$ for all subsegments of $a$ modulo $10^9+7$.

给你一个数组 $a_1, a_2, \dots, a_n$，其中所有 $a_i$ 两两互不相同。

我们定义函数 $f(l, r)$ 如下：

• 定义数组 $b_1, b_2, \dots, b_{r - l + 1}$，其中 $b_i = a_{l - 1 + i}$；
• 将数组 $b$ 按升序排序；
• 函数 $f(l, r)$ 的结果为 $\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$。

请计算 $\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$，即对数组 $a$ 的所有连续子段（子数组）计算 $f(l, r)$ 的总和，再对 $10^9+7$ 取模。

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$, $a_i \neq a_j$ for $i \neq j$) — array $a$.

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$，且当 $i \neq j$ 时 $a_i \neq a_j$）——数组 $a$。

Print one integer — the total sum of $f$ for all subsegments of $a$ modulo $10^9+7$

输出一个整数——所有子段的 $f$ 值之和对 $10^9+7$ 取模的结果。

Description of the first example:

• $f(1, 1) = 5 \cdot 1 = 5$;
• $f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$;
• $f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$;
• $f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$;
• $f(2, 2) = 2 \cdot 1 = 2$;
• $f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$;
• $f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$;
• $f(3, 3) = 4 \cdot 1 = 4$;
• $f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$;
• $f(4, 4) = 7 \cdot 1 = 7$;

第一个示例的说明：

• $f(1, 1) = 5 \cdot 1 = 5$；
• $f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$；
• $f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$；
• $f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$；
• $f(2, 2) = 2 \cdot 1 = 2$；
• $f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$；
• $f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$；
• $f(3, 3) = 4 \cdot 1 = 4$；
• $f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$；
• $f(4, 4) = 7 \cdot 1 = 7$；