Scalar Queries

2000ms

262144K

Description:

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

Input:

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

Output:

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

Sample Input:

4
5 2 4 7

Sample Output:

Sample Input:

3
123456789 214365879 987654321

Sample Output:

582491518

Note:

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

Informação

Provedor Codeforces

Código CF1167F