Palindrome Bo

Problem Description

There is an array with $n$ elements named $a$.If $seq$ is a palindrome subsequence of $a$,whose elements are increasing from the middle to both ends,then we call it a BoBo sequence. Two BoBo sequence are considered different if and only if they have different length or there is at least one position has a different number. Your task is to calculate how many different longest BoBo sequence are there in $a$.

Input

There are several test cases. The first line contains an integer $n$. The second contains $n$ numbers indicating $a_i$. $1\leq n\leq 5000,1\leq a_i\leq 20000$

Output

One line two number indicating the length of the longest BoBo sequence and the quantity of them. answer mod 10^9+7

Sample Input

5
1 1 1 1 1
5
2 2 3 2 2

Sample Output

5 1
4 1

Author

绍兴一中

Source

2016 Multi-University Training Contest 3