C语言等级考试四级真题：最长上升子序列。

一个数字序列$b_i$，当$b_1 < b_2 < ... < b_S$时，我们称这个序列是严格上升的。对于给定的序列$(a_1, a_2, ..., a_N)$，其上升子序列满足$1 \leq i_1 < i_2 < ... < i_K \leq N$且对应元素严格递增。例如序列(1,7,3,5,9,4,8)的上升子序列有(1,7)、(3,4,8)等，其中最长上升子序列长度为4（如(1,3,5,8)）。请你求解给定序列的最长上升子序列的长度。

输入

第一行输入序列的长度$N$（$1 \leq N \leq 100$），第二行输入$N$个整数，数值范围为$[0, 1000000]$。

输出

输出一个整数，表示最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4