题目描述

给定正整数序列，选择若干保持原先相对顺序的元素，使它们从前到后不下降（允许相等）。求最多能选择的元素个数。

输入格式

第一行 $N$，第二行 $N$ 个正整数。

输出格式

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

样例

8
1 3 1 5 9 7 4 8

5

数据范围

$1\le N\le100000$，$1\le a_i\le10^9$。