← 返回题目列表

Codeforces · 1621/G

G. 加权递增子序列

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

给定长度为 $$$n$$$ 的整数序列 $$$a_1, a_2, \ldots, a_n$$$。

长度为 $$$k$$$ 的索引序列 $$$i_1 < i_2 < \ldots < i_k$$$ 表示序列 $$$a$$$ 的长度为 $$$k$$$ 的子序列 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$。

如果对于每个 $$$1 \leq j < k$$$,$$$a_{i_j} < a_{i_{j+1}}$$$,则序列 $$$a$$$ 的长度 $$$k$$$ 的子序列 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 被称为递增子序列。

序列$$$a$$$长度为$$$k$$$的递增子序列$$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$的权重是$$$1 \leq j \leq k$$$的个数,使得存在索引$$$i_k < x \leq n$$$并且$$$a_x > a_{i_j}$$$。

例如,如果 $$$a = [6, 4, 8, 6, 5]$$$,则索引序列 $$$i = [2, 4]$$$ 表示序列 $$$a$$$ 的递增子序列 $$$[4, 6]$$$。这个递增子序列的权重是 $$$1$$$,因为对于 $$$j = 1$$$ 存在 $$$x = 5$$$ 和 $$$a_5 = 5 > a_{i_1} = 4$$$,但对于 $$$j = 2$$$ 这样的 $$$x$$$ 不存在。

求 $$$a$$$ 模 $$$10^9+7$$$ 的所有递增子序列的权重总和。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 序列 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 序列 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印所有递增子序列 $$$a$$$ 模 $$$10^9+7$$$ 的权重总和。

示例

输入 #1

4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5

输出 #1

4
12
0
6

注意

在第一个测试用例中,$$$a$$$ 的以下递增子序列的权重不为零:

- $$$[a_1] = [6]$$$ 的权重为 $$$1$$$。
- $$$[a_2] = [4]$$$ 的权重为 $$$1$$$。
- $$$[a_2, a_3] = [4, 8]$$$ 的权重为 $$$1$$$。
- $$$[a_2, a_4] = [4, 6]$$$ 的权重为 $$$1$$$。

在第二个测试用例中,$$$a$$$ 的权重不为零的 $$$7$$$ 递增子序列:$$$3$$$ 的权重为 $$$1$$$、$$$3$$$ 的权重为 $$$2$$$ 和 $$$1$$$ 的权重为 $$$3$$$。权重总和为$$$12$$$。