Question
Counting the Longest Rising Paths
You are given a sequence of KaTeX can only parse string typed expression integers written in a line. Imagine you are walking along this line from left to right, choosing some numbers to form a sequence. Each time you pick a number, the next number you choose must be strictly larger than the previous one, and you must always move forward in the line.
Your goal is to form the longest possible increasing sequence using this rule. However, there may be multiple different ways to form such a longest sequence.
Your task is to find how many distinct longest increasing subsequences can be formed from the given array.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of elements in the sequence.
The second line contains KaTeX can only parse string typed expression integers, representing the sequence KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the sequence KaTeX can only parse string typed expression.
Output
Print a single integer — the number of longest increasing subsequences that can be formed.
Example
Input
5
1 3 5 4 7
Output
2
Explanation
While walking through the sequence, the longest increasing path you can form has length 4.
There are two such longest paths:
Choosing KaTeX can only parse string typed expression
Choosing KaTeX can only parse string typed expression
Hence, there are 2 longest increasing subsequences in total.
5
1 3 5 4 7
Output
2
Explanation
While walking through the sequence, the longest increasing path you can form has length 4.
There are two such longest paths:
Choosing KaTeX can only parse string typed expression
Choosing KaTeX can only parse string typed expression
Hence, there are 2 longest increasing subsequences in total.