题目描述

给定$n$个数，求这$n$个数的最长上升子序列的长度。

输入格式

第一行有一个正整数$n$

第二行有$n$个正整数

输出格式

一个正整数，为最长上升子序列的长度。

样例

7
3 6 4 2 5 8 5

4

说明/提示

对于$10$%的数据，$n \leq 10$

对于$20$%的数据 $n \leq 20$

对于$50$%的数据 $n \leq 2000$

对于$100$%的数据，$n \leq 200000$，所有数都是不超过$10^9$的正整数