Scalar Queries
题意翻译
## 题目描述
给出一个数组$a_1,a_2,...,a_n$，其中所有元素两两不同。
定义函数$f(l,r)$：
- 定义数组$b_1,b_2,...,b_{r-l+1}$，其中$b_i=a_{l-1+i}$
- 将$b$按从小到大排序
- 则此时函数的值是$\sum\limits_{i=1}^{r-l+1}{b_i}\cdot i$
请计算对于所有满足$1 \le l \le r \le n$的$l$和$r$，$f(l,r)$的和。
由于结果可能很大，请输出对$10^9+7$取模的值。
## 输入输出格式
### 输入格式：
第一行包含一个整数$n$，即给定数组的长度。
第二行包含$n$个整数$a_1,a_2,...,a_n$，表示数组元素。
### 输出格式：
输出一个整数，表示答案对$10^9+7$取模的值。
## 说明
$1 \le n \le 5 \cdot 10^5$, $1 \le a_i \le 10^9$, 所有$a_i$两两不同。
样例1解释：
$ 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 $ ;
题目描述
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 $
输入输出样例
输入样例 #1
4
5 2 4 7
输出样例 #1
167
输入样例 #2
3
123456789 214365879 987654321
输出样例 #2
582491518
说明
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 $ ;