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: 2022-09-11 09:57:55

Why is the time limit so strict? O(N log N) with the recursive version of the data structure TLEs.

Edit: Finally AC after switching to the faster version of the data structure because I don't know how to code the recursive version of the data structure in my initial reply. Had to use two different versions of them and two pointers to compute the result. Offline testing on random big input showed this solution was 2/3 of the runtime of my original solution. It barely passed the time limit. Makes me wonder if the intended solution really is the iterative data structure.

Last edit: 2022-09-11 21:42:41
changyouren: 2021-10-01 11:27:07

think brute force and optimize

miloy23: 2021-06-28 07:51:13

any hints for this problem?

shervi: 2020-05-13 11:19:42

just need to care about the count.

Last edit: 2020-05-19 08:13:06
my99n: 2020-03-09 17:28:44

Sorry, first problem.

wisfaq: 2020-03-08 21:14:47

Last edit: 2020-03-09 13:42:47
Francky: 2020-03-08 19:13:27

@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: 2020-03-09 16:03:28
wisfaq: 2020-03-06 22:33:26

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: 2020-03-07 10:46:53
wisfaq: 2020-03-03 21:37:51

Last edit: 2020-03-03 21:40:52

Added by:Touch
Date:2020-02-26
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All