题目描述

给定长度为$n$的序列$a_i$，求其最长不下降子序列的长度。

不下降子序列是指这样的子序列，对于$i_1<i_2<i_3<…<i_k$，有$a_{i_1}\leq a_{i_2}\leq … \leq a_{i_k}$。

输入格式

第一行输入一个整数$n$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

4
1 3 2 4

样例输出 #1

3

说明/提示

对于40%的数据，有$1\leq n\leq 1000$。 对于100%的数据，有$1\leq n,a_i\leq 10^5$。