题目描述

又到了一年实习的时候了，『 21LostMemory 』有幸进入了互联网大厂百度实习。为了祝福大家也可以步步高升，他给大家出了一道非常经典的题目，希望这道简单的题目可以成为你上升之路的开始。

题目描述

有一个由 $n$ 正整数组成的序列，请你求出这个序列的最长上升子序列的长度。

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

输入格式

第一行，一个整数 $n$ ($1 \leq n\leq 5 \times 10^3$) 表示序列的长度

第二行， $n$ 个整数，第 $i$ 个数表示序列中第 $i$ 个数 $a_i$ ($10^{-18} \leq a_i\leq 10^{18}$)

输出格式

仅一行，表示最长上升子序列的长度

样例输入输出

6
3 1 2 4 3 5

4

5
1 2 3 4 5

5

样例解释

对于第一个样例，它的最长上升子序列是$[1,2,4,5]与[1,2,3,5]$，长度为$4$

字典序：字典序的比较是从两个序列的第一个数开始，按照数的大小进行比较。如果第一个数相同，则比较下一个数，依此类推，直到找到不同的数或者其中一个序列结束。