题目描述

在一个无序的序列 \(a_1,a_2,a_3,a_4…a_n\) 里，找到一个最长的序列满足：\(a_i<a_j<a_k…<a_m\) ,且 \(i<j<k…<m\)。

例如原序列为 \(1,5,8,3,6,7\) 得到最终栈为 \(1,3,6,7\)，最长递增子序列为长度 \(4\)。

格式

输入格式

第一行：一个正整数 \(N\)；

第二行：\(N\) 个整数（数据不超过\(int\)）；

输出格式

一个数，找到的最长上升序列长度；

样例1

样例输入1

7
1 7 3 5 9 4 8

样例输出1

4

限制

时间：\(1s\) 空间：\(64M\)

\(N<=1000\)