Problem1168-- V1205 CoVH之柯南购物

1168: V1205 CoVH之柯南购物

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

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

Input

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

Output

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

Sample Input Copy 

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

Sample Output Copy 

4
2

Source/Category

Copyright&nbsp by&nbsp [E.O.T][CoVH]Dragon.Dai  
[Submit] [Status]