Increasing Subsequence II

题目描述

给定一个由 n 个整数组成的数组，你的任务是计算其中包含的递增子序列的数量。如果两个子序列的数值相同但在数组中的位置不同，则它们分别计数。

输入格式

第一行输入一个整数 n：数组的大小。 第二行有 n 个整数 x_1,x_2,$\dots$,x_n：数组的内容。

输出格式

输出一个整数：递增子序列的数量对 $10^9+7$ 取模。

3
2 1 3

5

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ 样例解释：递增子序列为 [2], [1], [3], [2,3] 和 [1,3]。

标签: CSES1748|动态规划|DP

来源

CSES1748|动态规划|DP