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:2020-02-26
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-05-13 11:19:42
just need to care about the count.

Last edit: 2020-05-19 08:13:06
2020-03-09 17:28:44
Sorry, first problem.
2020-03-08 21:14:47 wisfaq


Last edit: 2020-03-09 13:42:47
2020-03-08 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: 2020-03-09 16:03:28
2020-03-06 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: 2020-03-07 10:46:53
2020-03-03 21:37:51 wisfaq


Last edit: 2020-03-03 21:40:52
2020-03-03 17:38:24 Simes
My my, how can we resist you?
2020-03-03 13:46:28 wisfaq
Mamma mia, here we go again...

Last edit: 2020-03-03 13:48:57
2020-03-02 09:17:16 Vipul Srivastava
Please remove the problem or enable the Submit button
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.