Submit  All submissions  Best solutions  Back to list 
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.
Added by:  Touch 
Date:  20200226 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
hide comments


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

20200309 17:28:44
Sorry, first problem. 

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

20200308 19:13:27 Francky
@psetter : you should have let a new comment after the fix of your issue, and not hide previous comments. Please unhide previous comment. =(Edit, Francky)=> Thanks to admins for the backup of comments. Last edit: 20200309 16:03:28 

20200306 22:33:26 wisfaq
What is the waiting for, admins? =(Francky)=> I've just an email... Please be patient. @psetter, you should read comments for your problems, and for new problems : read every day ! Last edit: 20200307 10:46:53 

20200303 21:37:51 wisfaq
Last edit: 20200303 21:40:52 

20200303 17:38:24 Simes
My my, how can we resist you? 

20200303 13:46:28 wisfaq
Mamma mia, here we go again... Last edit: 20200303 13:48:57 

20200302 09:17:16 Vipul Srivastava
Please remove the problem or enable the Submit button 