你有一个长度为 n 的数组 a[1],a[2],...,a[n] 。

你想找到最长的子序列满足如下条件：
• 它是一个回文子序列，长度是奇数或者偶数都可以。
• 这个子序列从中间开始是不降的。

比如一个长度为 2k 的序列 b[1],b[2],...,b[2k] ，需要满足 b[1]=b[2k], b[2]=b[2k-1], ... , b[k]=b[k+1] 并且 b[k+1]≤ b[k+2]≤ … ≤b[2k] 。

问满足条件的最长的子序列长度是多少，有多少个本质不同的最长子序列，由于答案很大，输出答案模 10^9+7 的值。两个子序列本质不同，当且仅当至少存在一个位置上数字是不同的。

第一行一个整数 n 。
接下来一行 n 个整数 a[1],a[2],..,a[n] 。

一行，包含两个整数，分别为最长的子序列长度，和本质不同的子序列个数。

5
3 3 1 2 3

3 3

样例解释
子序列分别为 {3,3,3},{3,1,3},{3,2,3} 。这里选第 1,3,5 个元素和选第2,3,5 个元素得到的序列相同，所以算同一个。

数据规模
共 10 组数据。
测试点 1,2 满足 n≤ 20。
测试点 3,4 满足 n≤ 100。
测试点 5,6 满足 1≤a[i]≤20。
对于 100%的数据，满足 1≤n≤5000,1 ≤a[i]≤n 。