← 返回题目列表

Codeforces · 1167/F

F. 标量查询

中文机器翻译题面 查看原题

给你一个数组 $$$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$$$ 模 $$$10^9+7$$$ 的所有子段的 $$$f$$$ 总和。

输入

第一行包含一个整数 $$$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$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$) — 数组 $$$a$$$。

输出

打印一个整数 — $$$a$$$ 的所有子段的 $$$f$$$ 的总和以 $$$10^9+7$$$ 为模

示例

输入 #1

4
5 2 4 7

输出 #1

167

输入 #2

3
123456789 214365879 987654321

输出 #2

582491518

注意

第一个示例说明:

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