问题 3468 --CoVH之柯南购物

3468: CoVH之柯南购物

题目描述

  有一天,鱼牛去超市买东西,他买东西有个很奇怪的特性:他买一件东西的价格一定要比上一件的低。现在给出超市里东西的价格,请问鱼牛如何选择才能购买到最多的东西呢?并请求出鱼牛买东西的方案数。
注:超市里有一条“购物路”,从头到尾有n件商品,每件商品只有一件,鱼牛不能回头购买。

输入

输入第一行是n(1< =n< =2000),表示超市里有n件商品
以下n行是超市里的“购物路”每件商品的价格,按顺序从头到尾。

输出

输出第一行是鱼牛能购买的最多的商品数 第二行是鱼牛购买商品的方案数除以10000的余数。

样例输入输出

输入#1 复制
12
68
69
54
64
68
64
70
67
78
62
98
87
输出#1 复制
4
2

提示

序号 标题 作者 发表时间 费用 订购数 操作