题目描述

设有由 $n$ 个不相同的整数组成的数列，记为: $a_1$、$a_2$、$\dots$、$a_n$ 且 $a_i \neq a_j$ ($i \neq j$)。

例如 $3$，$18$，$7$，$14$，$10$，$12$，$23$，$41$，$16$，$24$。

若存在 $i_1 \lt i_2 \lt i_3 \lt \dots \lt i_e$ 且有 $a$_$i1$$\lt a$_$i2$$\lt \dots \lt a$_$ie$，则称为长度为 $e$ 的不下降序列。

如上例中 $3$，$18$，$23$，$24$ 就是一个长度为 $4$ 的不下降序列，同时也有 $3$，$7$，$10$，$12$，$16$，$24$ 长度为 $6$ 的不下降序列。

程序要求，当原数列给出之后，求出最长的不下降序列。

输入

第一行为 $n$ ，表示 $n$ 个数 $(10 \le n \le 10000)$；

第二行 $n$ 个整数，数值之间用一个空格分隔 $(1 \le a_i \le n)$ ；

输出

最长不下降子序列的长度。

样例

3
1 2 3

3

来源

动态规划