Problem 4893. -- [Usaco2002 Feb]Buy Low Buy Lower

4893: [Usaco2002 Feb]Buy Low Buy Lower

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 17  Solved: 12
[Submit][Status][Web Board]

Description

“低价购买"这条建议是在股票市场取得成功的一半规则。要想被认为是公认的股票之神, 
你必须遵循以下的问题建议: 
"低价购买;再低价购买" 
每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是 
在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的 
出售价(2 范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循"低价购买;再低价购买"的原则。 
写一个程序计算最大购买次数。 
这里是某支股票的价格清单: 
日期 1 2 3 4 5 6 7 8 9 10 11 12 
价格 68 69 54 64 68 64 70 67 78 62 98 87 
最优秀的投资者可以购买最多4次股票,可行方案中的一种是: 
日期 2 5 6 10 
价格 69 68 64 62 

Input

*第1行: N (1 <= N <= 5000),股票发行天数 
*第2行: N个数,是每天的股票价格。 

Output

仅一行两个数: 
? 最大购买次数 
? 拥有最大购买次数的方案数(<=2 ) 

Sample Input

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

当2种方案“看起来一样“时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。
如5 4 3 2 1 5 4 3 2 1中就只包含一种符合题目要求的方案。

Sample Output

4 2

HINT

Source

[Submit][Status]