Counting Longest Increasing Subsequences (Bonus)

Problem Description

This problem is a strengthened version of daimayuan problem 326; the only difference is the ranges of $n$ and $a_i$.

Finding the length of the longest increasing subsequence is quite well known. Here, you are asked to compute the number of longest increasing subsequences.

Two ordered tuples are considered different if they differ in at least one value. For example, in $[1, 3, 3, 0, 4]$, the subsequence $[1, 3, 4]$ using the first $3$ and the subsequence $[1, 3, 4]$ using the second $3$ count as two distinct answers.

Input Format

The input consists of two lines. The first line contains an integer $n$, the size of the sequence $\{a\}$.

The second line contains $n$ integers separated by spaces, representing $a_1, a_2, \dots, a_n$ in order.

Output Format

Output the number of longest increasing subsequences.

Since this value may be very large, output it modulo $10^9 + 7$.

Sample Input 1

5
1 3 3 0 4

Sample Output 1

2

Sample Input 2

8
1 2 4 2 4 7 3 4

Sample Output 2

5

Explanation

The answers consist of:

$[1, 2, 4, 7] \times 3$

$[1, 2, 3, 4] \times 2$

Constraints

• $1 \le n \le 4 \times 10^5$
• $a_i \in [-10^8, 10^8]$