#P1819. 又见最长单调递增子序列

又见最长单调递增子序列

给一个序列 X(x[1] , x[2] , x[3] ……) ,可以找出他的任意一个单调递增子序列如 x[i1] , x[i2] , x[i3] …… x[in]

它必须满足以下条件。

(1) X[i1] < X[i2] < …… < X[in];

(2) 1<= i1 <i2 < …… < in <= n

问题是:

(1)找到最长的单调递增子序列 ,输出长度 len

(2)在每个元素最多只能用一次的情况下,找出长度为len 的单调递增子序列有多少个,输出个数sum。

Input

多组测试数据,不超过100组.
每组输入数据包含两行。
第一行一个数字n,代表序列的长度,第二行包含 n 个数字ai,代表序列中每个元素的值。
n <= 500 , ai <= 10000

Output

每组测试数据输出有两行。第一行输出len,第二行输出sum。

Sample Input

4
3 6 2 5

Sample Output

2
2

HINT

Source