题目描述

给定一个长度为 $n$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

7
3 1 2 1 8 5 6

4

数据范围

对于基础数据( $100pts$ )

$n \le 5000 , a \le 10^9$

对于附加数据( 另外 $100pts$ )

$n \le 100000, a \le 10^9$