A12614 | 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$ .

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$ .

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