Maximal Longest Increasing Subsequence Count

Marton’s friend Cero has an array of (N) positive integers: (A_1, A_2, \dots, A_N). The process is as follows. First, Cero writes the first number (A_1) on the blackboard. Then for each (i=2,3,\dots,N), he writes (A_i) on either the left or the right end of the current sequence. Note that even if two final sequences have the same list of numbers, they are considered different if the order in which the numbers were written differs. For example, with the array [1, 1] the sequence obtained by writing the second 1 on the left of the first 1 is considered different from the one obtained by writing it on the right.\n\nLet a sequence be the final arrangement of numbers. In each such sequence, consider its longest strictly increasing subsequences (LIS) (a subsequence (a_{i_1}, a_{i_2}, \dots, a_{i_k}) is strictly increasing if (a_{i_1} < a_{i_2} < \cdots < a_{i_k})).\n\nDefine (M) to be the maximum possible length of the longest increasing subsequence among all sequences that can be formed by Cero’s process. Among those sequences whose longest increasing subsequence has length exactly (M), let the value for each sequence be the number of distinct longest increasing subsequences that appear in it (note that different occurrences are counted separately). The task is to compute the sum of these numbers over all sequences achieving the maximum length (M), and report the result modulo (10^9+7).\n\nMore formally, given the array (A), for each of the (2^{N-1}\n) possible sequences (determined by placing (A_i) (for (i\ge2)) either on the left or right of the already written part), compute the length of its longest strictly increasing subsequence and the total count of such subsequences. Let (M) be the maximum LIS length among all sequences. You are to output (M) and the sum of the counts of longest increasing subsequences for all sequences whose LIS length is equal to (M), modulo (10^9+7).

inputFormat

The first line contains an integer (N) (the number of elements).\nThe second line contains (N) positive integers (A_1, A_2, \dots, A_N) separated by spaces.

outputFormat

Output two integers separated by a space: (M) (the maximum length of a longest increasing subsequence among all generated sequences) and the sum (modulo (10^9+7)) of the counts of longest increasing subsequences for all sequences with longest increasing subsequence length equal to (M).

sample

2
1 1

1 4