#3437. 低买 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

给定一段时间内股票的每日售价(正16位整数)。

你可以选择在任何一天购买股票。

每次你选择购买时,当前的股票价格必须严格低于你之前购买股票时的价格。

编写一个程序,确定你应该在哪些天购进股票,可以使得你能够购买股票的次数最大化。

例如,下面是一个股票价格时间表:

Day   1  2  3  4  5  6  7  8  9 10 11 12

Price 68 69 54 64 68 64 70 67 78 62 98 87

如果每次购买都必须遵循当前股票价格严格低于之前购买股票时的价格,那么投资者最多可以购买四次该股票。

买进方案之一为:

Day    2  5  6 10

Price 69 68 64 62

输入格式

第1行包含整数 N,表示给出的股票价格的天数。

第2至最后一行,共包含 N 个整数,每行10个,最后一行可能不够10个,表示 N 天的股票价格。

同一行数之间用空格隔开。

输出格式

输出占一行,包含两个整数,分别表示最大买进股票次数以及可以达到最大买进次数的方案数。

如果两种方案的买入日序列不同,但是价格序列相同,则认为这是相同的方案(只计算一次)。

样例

样例输入1

12
68 69 54 64 68 64 70 67 78 62
98 87

样例输出1

4 2

样例输入2

5
4 3 2 1 1

样例输出2

4 1

数据范围与提示

POJ 1952