暂无测试数据。

题目描述

给定一个 \(n\) 个数的序列 \(A\)，
问最长的不下降子序列长度为多少。

对于一个序列 \(p_1 < p_2 < … < p_k\),
其为不下降子序列需要满足：
\(A[p_1] \leq A[p_2] \leq A[p_3] \leq … \leq A[p_k]\)。

输入

第一行，一个整数 \(n\)。
接下来一行 \(n\) 个整数，表示 \(A[i]\)。

输出

一个整数，表示最长的不下降子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4

数据范围限制

\(n \leq 5000\),\(|A[i]| \leq 10^6\)。

来源

基础篇例7.10