题目描述

若一个序列满足$a_1$<$a_2$<$…$<$a_n$，则该序列是有序$（$上升$）$的。

设给定数字序列$($$a_1$,$a_2$,…,$a_n$$)$的子序列为任意序列$($$ai_1$,$ai_2$,…,$ai_k$$)$，其中$1$$≤$$i_1$$<$$i_2$$<$…$<$$i_k$$≤$$n$，例如序列$($$1$,$7$,$3$,$5$,$9$,$4$,$8$$)$有上升子序列如$($$1$,$7$$)$、$($$3$,$4$,$8$$)$和其他子序列。

所有最长的上升子序列的长度都是$4$，例如$($$1$,$3$,$5$,$8$$)$。

当给定数字序列时，找到其最长上升子序列的长度。

输入格式

第$1$行包含序列的长度$n$；第$2$行包含序列的$n$个元素，每个元素都为$0$～$1$$0$$0$$0$$0$的整数。

输出格式

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

样例

7
1 7 3 5 9 4 8

4

数据范围

$1≤n≤1000$

来源

POJ2533