题目描述

给定一个长度为 $n$ 的序列 $a = \{ a_1, a_2, \ldots,a_n \}$。求：序列 $a$ 的最长上升子序列的长度。

换句话说，你需要找到一个最长的下标序列 $i_1, i_2, \ldots, i_k$，满足：

1. $1 \le i_1 \lt i_2 \lt \ldots \lt i_k$
2. $a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_k}$

并输出序列长度。

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

输出格式

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

样例

5
3 2 5 4 8

3

8
6 2 5 2 3 3 7 8

4

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 20$，$a_i \le 100$
• 对于 $40\%$ 的数据，$n \le 2000$，$a_i \le 10^5$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$