题目描述

某农场有一个由按编号排列的 $n$ 根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩的高度成一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数（即非降序）。

试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数最多，并求出达到最多木桩数的不同选取方案数。

输入格式

第一行只有一个整数 $m$，表明随后有 $m$ 个问题的描述信息。

接下来 $m$ 行，每行描述一个问题，格式为 $n, h_1, h_2, h_3, \dots, h_n$，其中 $h_i$ 表示第 $i$ 根木桩的高度。

输出格式

依次输出每个问题的解，每行输出两个整数，分别表示最多能选取的木桩数量和达到该数量的方案数。

样例

3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12

4 1
2 2
3 3

数据范围与提示

• $1 \le m \le 5$
• $1 \le n \le 20$
• $1 \le h_i \le 150$

来源

CSPJ-重点算法班