本题是 http://oj.daimayuan.top/problem/326 的加强版,差别仅在于 $n$ 与 $a_i$ 的取值。
求最长上升子序列及其长度的问题已经相当普及,本题希望你求解 最长上升子序列的个数。
只要有序元组有一个值不同,就称不同。如 $[1, \color{green}{3}$ $,\color{red}{3}$ $, 0, 4]$ 中 $[1, \color{green}{3}$ $, 4], [1,\color{red}{3}$ $, 4]$ 算作两个答案。
输入格式
输入包含两行,第一行有一个整数 $n$,表示序列 $\{a\}$ 的大小。
接下来一行包含 $n$ 个用空格分隔的整数,依次表示 $a_1, a_2, \cdots, a_n$。
输出格式
输出最长上升子序列的个数。
由于这个值可能很大,你只需要输出其模余 $10^9 + 7$ 的结果。
数据规模
- $1 \le n \le 4 \times 10 ^ 5$
- $a_i \in [-10 ^ 8, 10 ^ 8]$
样例 1 输入
5
1 3 3 0 4
样例 1 输出
2
样例 2 输入
8
1 2 4 2 4 7 3 4
样例 2 输出
5
解释:
共包含:
$[1, 2, 4, 7] \times 3$
$[1, 2, 3, 4] \times 2$