HMLIS  HowManyLis
The task is simply to find LIS and number of way we can select distinct LIS
Definition :
LIS (short for Longest Increasing Subsequence) is the longest subsequence of the sequence in which every element in the subsequence is increasing.
an LIS is distinct when one of the element come from different index of the beginning array.
this task involve finding length of Longest IS and number of way LIS can be made.
Input
First line : integer N represent number of elements in the sequence N <= 100000
Second line : N integers represent number in the sequence, each integer is in the range [1, 100000000]
Output
2 integer in 1 line, Lenght of LIS and Number of LIS that can be made.
The ans can be very large, so print both ans mod 1000000007
Example
Input:5 1 3 2 5 4
Output:3 4 // Explanation : the subsequence are // (1, 3, 5), (1, 3, 4), (1, 2, 5), (1, 2, 4)
Input:5 1 2 5 3 3
Output:3 3 // Explanation : the subsequence are // (1, 2, 5), (1, 2, 3), (1, 2, 3) // note that there're two 3 in the sequence which count seprerately.
hide comments
sxie12:
20220911 09:57:55
Why is the time limit so strict? O(N log N) with the recursive version of the data structure TLEs.


changyouren:
20211001 11:27:07
think brute force and optimize 

miloy23:
20210628 07:51:13
any hints for this problem? 

shervi:
20200513 11:19:42
just need to care about the count. Last edit: 20200519 08:13:06 

my99n:
20200309 17:28:44
Sorry, first problem. 

wisfaq:
20200308 21:14:47
Last edit: 20200309 13:42:47 

Francky:
20200308 19:13:27
@psetter : you should have let a new comment after the fix of your issue, and not hide previous comments.


wisfaq:
20200306 22:33:26
What is the waiting for, admins?


wisfaq:
20200303 21:37:51
Last edit: 20200303 21:40:52 
Added by:  Touch 
Date:  20200226 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 