最长上升子序列4

题目描述

给出一个由n个数组成的序列A[1..n]，求最长单调上升子序列（LIS)的长度。LIS即求最大的一个子序列长度m，使得a₁<a₂<……<a_m且A[a₁]<A[a₂]<……<A[a_m]。

输入说明

两行：

第1行：整数n (1<=n<=1000)

第2行：n个整数 （int范围内），空格隔开。

输出说明

一行：一个整数，即最长上升子序列长度。

样例

输入

10
63	11	21	36	28	20	57	37	82	4

输出

5