Start: Apr, 12, 2024 15:00:00
20240412动态规划复习
End: May, 12, 2024 19:00:00
Time elapsed:
Time remaining:

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

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:32     AC:12     Score:100


Description

设有由 $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$ 的不下降序列。

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

Input

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

Output

最长不下降子序列的长度

Samples

input:
3 1 2 3
output:
3