OI题库

给出一个由n个数组成的序列x[1..n]，找出它的最长单调上升子序列。即求最大的m和a1,a2……,am，使得a1<a2<……<am且x[a1]<x[a2]<……<x[am]。

例：x[]={3,4,5,6,8,7,5,3,5,9};则最长的单调上升子序列长度是：6，这时m为6，a1=0,a2=1,a3=2,a4=3,a5=4或者是5都可以，a6=9，可以满足x[a1]<x[a2]<……<x[am]（这时的最长单调递增子系列是3,4,5,6,8或者7,9，该子系列长度是6）

输入：

第一行为一个整数n,第二行为n个整数，表示一个长度为n的整数系列。

输出：

一个整数m，表示该整数系列的最长子系列的长度。

输入样例：

10

3 4 5 6 8 7 5 3 3 9

输出样例：

6