题目描述

给出一个由 \(n\) 个数组成的序列。请输出这个序列的 最长上升子序列 的长度。

最长上升子序列是指，从原序列中 按顺序 取出一些数字排在一起，这些数字是 逐渐增大 的。

输入格式

第一行，一个整数 \(n\)，表示序列长度。

第二行有 \(n\) 个整数，表示这个序列。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

6
1 2 4 1 3 4

样例输出 #1

4

样例解释 #1

分别取出 \(1\)、\(2\)、\(3\)、\(4\) 即可。

提示

【数据范围】

对于 \(30\%\) 的数据，满足 \(1\le n\le10^3\)。
对于 \(100\%\) 的数据，满足 \(1\le n\le10^5\)，原序列中的每个数均为 \([-10^9,10^9]\) 的范围内的整数。