题目描述

你有一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。

你想找到最长的子序列满足如下条件：

• 它是一个回文子序列，长度是奇数或者偶数都可以。
• 这个子序列从中间开始是不降的。

比如一个长度为 $2k$ 的序列 $b_1, b_2, \dots, b_{2k}$，需要满足
$b_1 = b_{2k}, b_2 = b_{2k-1}, \dots, b_k = b_{k+1}$ 并且 $b_{k+1} \le b_{k+2} \le \dots \le b_{2k}$。

问满足条件的最长的子序列长度是多少，有多少个本质不同的最长子序列。
由于答案很大，输出答案模 $10^9 + 7$ 的值。

两个子序列本质不同，当且仅当至少存在一个位置上数字不同。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

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

输入输出样例 #1

输入 #1

5
3 3 1 2 3

输出 #1

3 3

说明/提示

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

共 $10$ 组数据。

测试点 $1,2$ 满足 $n \leq 20$。

测试点 $3,4$ 满足 $n \leq 100$。

测试点 $5,6$ 满足 $1 \leq a_i \leq 20$。

对于 $100\%$ 的数据，满足 $1 \leq n \leq 5000,1 \leq a_i \leq n$。