一、链表（每一功能用一函数实现）

1、 建立n个结点（结点数据域的值由键盘输入）构成的单链表。

2、 查找数据域值为x的结点，若找到，返回该结点的地址。

1、 在数据域值为x的结点之前插入一数据域值为y的结点，若表中无数据域值为x的结点，则将数据域值为y的结点插入表尾。

(一) 木桩问题

某农场有一个按编号次序排列的n根木桩构成的首位不相连接的围栏。现欲在这个围栏中选取一些木桩，按照原有的编号次序排列之后这些木桩的高度成为一个升序序列。所谓升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选取出t根木桩的方案的种数c。

例如：围栏由高度分别为10，1，9，8，7，6，3，4，6的木桩构成，则选出高度为1，3，4，6的木桩是满足题意的选取方案。

输入：文件中的第一行只有一个数m，表明随后有m个问题的描述信息，每个问题的描述信息格式为n h1 h2 h3····hn。（其中hi（i=1，2，····n）表示第i根木桩的高度）。

输出：依次输出每个问题中t和c的解。每行输出一个问题的解。

示例：

输入

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

(一) 木桩问题

某农场有一个按编号次序排列的n根木桩构成的首位不相连接的围栏。现欲在这个围栏中选取一些木桩，按照原有的编号次序排列之后这些木桩的高度成为一个升序序列。所谓升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选取出t根木桩的方案的种数c。

例如：围栏由高度分别为10，1，9，8，7，6，3，4，6的木桩构成，则选出高度为1，3，4，6的木桩是满足题意的选取方案。

输入：文件中的第一行只有一个数m，表明随后有m个问题的描述信息，每个问题的描述信息格式为n h1 h2 h3····hn。（其中hi（i=1，2，····n）表示第i根木桩的高度）。

输出：依次输出每个问题中t和c的解。每行输出一个问题的解。

示例：

输入

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