C. (L3-11)最长不下降子序列

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

设有由 $n$ 个不相同的整数组成的数列，记为: $a(1)、a(2)、……、a(n)$ 且 $a(i)!=a(j) (i!=j)$

例如 $3，18，7，14，10，12，23，41，16，24$。若存在 $i1<i2<i3< \dots < ie$ 且有 $a(i1)\leq a(i2) \leq … \leq a(ie)$ 则称为长度为 $e$ 的不下降序列。

如上例中 $3，18，23，24$ 就是一个长度为 $4$ 的不下降序列，同时也有 $3，7，10，12，16，24$ 长度为 $6$ 的不下降序列。

程序要求，当原数列给出之后，求出最长的不下降序列。

第一行为 $n$，表示 $n$ 个数($10 \leq n \leq 10000)$
第二行 $n$ 个整数，数值之间用一个空格分隔 $(1 \leq a(i) \leq n)$

最长不下降子序列的长度

3
1 2 3