题目描述

给出一个由 $n(n\le 10000)$ 个不超过 $10^3$ 的正整数组成的序列。请输出这个序列的最长上升子序列的个数。

注意 这个数列必须是 严格 递增的。

输入格式

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

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

5
1 3 5 4 7

2

提示

解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。