回文子序列

题目描述 你有一个长度为�的数组�1 , �2 , …, �� 。

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

• 它是一个回文子序列，长度是奇数或者偶数都可以。

• 这个子序列从中间开始是不降的。

比如一个长度为 2�的序列�1 , �2 , …, �2�，需要满足�1 = �2� , �2 = �2�−1 , …, �� = ��+1 并且��+1 ≤ ��+2 ≤ … ≤ �2� 。

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

输入格式 第一行一个整数�。

接下来一行�个整数�1 , �2 , …, �� 。

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

样例输入 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 个元素得 到的序列相同，所以算同一个。

样例输入输出 2 见下发文件。

数据规模 共 10 组数据。

测试点 1,2 满足� ≤ 20。 测试点 3,4 满足� ≤ 100。

测试点 5,6 满足 1 ≤ �� ≤ 20。

对于 100%的数据，满足 1 ≤ � ≤ 5000,1 ≤ �� ≤ �。