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 >
	wisfaq: 2020-03-03 13:46:28 Mamma mia, here we go again... Last edit: 2020-03-03 13:48:57
	Vipul Srivastava: 2020-03-02 09:17:16 Please remove the problem or enable the Submit button
	nadstratosfer: 2020-02-27 16:04:10 Please state limit on n and enable submissions.