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.