502 - 最长上升子序列(LIS)

通过次数

102

提交次数

216

时间限制 : 1 秒
内存限制 : 128 MB

对于一串数A={a_1,a_2,a_3…a_n},它的子序列为S={s_1,s_2,s_3…s_n},满足 {s_1 < s_2 < s_3 < … < s_m} 。求A的最长子序列的长度。

输入

第一行是一个整数n(1<=n<=1000)

第二行是n个数,每个数之间以一个空格隔开。每个数的范围均在int型范围内。

输出

输出最长上升子序列的长度。

样例

输入

5
3 5 4 2 1

输出

2

提示

【数据规模】

100\%的数据,满足1≤n≤1000