3870 - 最长递增子序列

求一个序列的最长递增子序列。 
 

比5 4 1 3 2 
 

最长的递增的子序列为1 3或者1 2 
 

输入

第一行输入一个整数n 
 

第二行输入n个整数 
 

输出

输出一个整数,表示最长递增子序列的长度

样例

输入

5
5 4 3 2 1

输出

1

提示

1<=n<=1000,1<=序列元素<=10000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题