题目描述

设有由 $n$ 个不相同的整数组成的数列，记为：$a_{1},a_{2},...,a_{n}$，例如 $3,18,7,14,10,12,23,41,16,24$。若存在 $i1<i2<i3< \cdots < ie$ 且有 $a_{i1}<a_{i2}<\cdots <a_{ie}$ 则称为长度为 $e$ 的不下降序列。如上例中 $3,18,23,24$ 就是一个长度为 $4$ 的不下降序列，同时也有 $3,7,10,12,16,24$ 长度为 $6$ 的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。

输入格式

第一行为 $n$，表示 $n$ 个数

第二行 $n$ 个整数，数值之间用一个空格分隔

输出格式

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

样例

3
1 2 3

3

解释#1

$1 2 3$ 构成了最长的不下降子序列，总个数为 $3$

7
1 7 3 5 9 4 8

4

解释#2

$1 3 5 9$ 构成了最长的不下降子序列，总个数为 $4$

数据范围

$n < 1000$