题目描述

（LIS问题）给定一个序列，从中选取若干个数，使得这一组数组成上升子序列尽可能长，即对于所有的 $i \lt j$ 满足 $a_i \lt a_j$ ，求这个序列的最长上升子序列的长度。

输入格式

第一行一个整数 $n$ 表示序列的长度

接下来一行 $n$ 个整数表示序列

输出格式

一行一个整数表示最长上升子序列的长度

样例

样例输入

5
1 5 1 2 4

样例输出

3

数据范围与提示

组成的数列为 $1$ $2$ $4$，不存在比这个更长的上升子序列

• 对于 $30\%$ 的数据， $n \le 2000$

• 对于 $100\%$ 的数据，$n \le 100000$