5827 - 最长不下降子序列

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 64 MB

输入一个数组 $a_1，a_2，\dots，a_n$ ，找到最长的不降子序列 $a_b$ $_1$ ≤ $a_b$ $_2$ ≤…≤ $a_b$ $_k$ ，其中 $b_1$ < $b_2$ < ... < $b_k$ 。请计算最长的不下降子序列的长度。例如输入为：8 3 4 4 6 5，最长不下降子序列长度为4，有两组，分别为3 4 4 5或3 4 4 6.

输入

第一行为一个正整数n。

第二行为n个整数，用空格隔开。

输出

最长不下降子序列的长度。

样例

输入

5
9 3 6 2 7

输出

提示

对于100%的数据， $n\le 2000$ 。

来源

课课通