题目描述

设由 $n$ 个两两不相同的整数组成的数列，记为: $a_1, a_2, \dots, a_n$。

例如3，18，7，14，10，12，23，41，16，24。若存在 $i_1<i_2<i_3<… < i_k$ 且有 $a_{i_1} <a_{i_2} < \dots < a_{i_k}$ 则称为长度为 $k$ 的上升子序列。

如上例中 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