The task is simply to find LIS and number of way we can select distinct LIS

LIS (short for Longest Increasing Subsequence) is the longest subsequence of the sequence in which every element in the subsequence is increasing.

A LIS is distinct when one of the element come from different index of the beginning array.

This task involves finding length of Longest IS and number of ways LIS can be made.

Input

First line: integer Nrepresent 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, Length of LIS and Number of LIS that can be made.

The answers can be very large, so print both answers mod 1000000007.

Examples

Input:
5
1 3 2 5 4

Output:
3 4

Input:
5
1 2 5 3 3

Output:
3 3

Explanation

In the first test case, the subsequence are (1, 3, 5), (1, 3, 4), (1, 2, 5), (1, 2, 4).

In the second test case, the subsequence are (1, 2, 5), (1, 2, 3), (1, 2, 3). Note that there are two 3s in the sequence which both count separately.

---

hide comments

< Previous 1 2 Next >
	harsh_bhar0629: 2024-04-20 16:43:35 Nice Question of Segment Tree(query-on-prefix-array)
	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.
	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
	Simes: 2020-03-03 17:38:24 My my, how can we resist you?