题目描述

最长递增（上升）子序列（longest  increasing subsequence）是动态规划中的一个经典问题。

给定长为n序列，如1、5、2、3、11、7、9，从中选取一个子序列，这个子序列需要单调递增，问最长的上升序列（LIS）长度是多少。

输入格式

第一行N，表示原数列中数的个数（n<100000）
第二行有n个数

输出格式

一行，表示抽出的序列最大长度

样例

input

7
1 7 3 5 9 4 8

output

4

提示

1 7 3 5 9 4 8  
从这7个数可以抽出 1 3 5 9 四个数构成最长序列，从这7个数可以也可以抽出 1 3 4 8 四个数构成最长序列 
最长递增序列长度为4