|| ||Code Submission Evaluation System
CSES Problem Set
Increasing Subsequence II
Task | Statistics
CSES - Increasing Subsequence IICSES - Increasing Subsequence II
|Time limit:||1.00 s
||Memory limit:||512 MB|
Given an array of $n$ integers, your task is to calculate the number of increasing subsequences it contains. If two subsequences have the same values but in different positions in the array, they are counted separately.
The first input line has an integer $n$: the size of the array.
The second line has $n$ integers $x_1,x_2,\dots,x_n$: the contents of the array.
Print one integer: the number of increasing subsequences modulo $10^9+7$.
- $1 \le n \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
2 1 3
Explanation: The increasing subsequences are $$, $$, $$, $[2,3]$ and $[1,3]$.