题目描述

给定一个长度为 $n$ 的正整数序列，求其 最长上升子序列 的长度（严格递增）。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个正整数。

输出格式

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

5
1 2 3 4 5

5

8
1 3 5 2 4 6 8 7

5

数据范围

• $1 \le n \le 5000$
• 每个数 $\le 10^6$