题目描述

POJ 2533

邪狼:"怎么感觉这些机器人比我还聪明?不是说人工智能永远不能超越人类吗?" 天顶星人:"你们真是目光短浅,自大而愚蠢!你要知道，如果有意识的智慧生命在无 穷无尽的岁月里居然做不到无意识的宇宙曾做过的事(产生智慧生命),这就好像一只无知 的猴子在琴键上跳了亿万年居然跳出了一支贝多芬第九交响曲$\red{,}$而有智慧的生物居然几千 年也学不会一支简单的小夜曲那样荒谬。如果说永远都做不到$\red{,}$那这在你们的哲学里,不就 是神秘论和不可知论了吗?要知道世事无绝对。" 话说在天顶星人的指导下,修罗王建造了一支机器人军团，机器人排成一行,且身高分 别为$\red{b_1,b_2,...,b_n}$。修罗王准备从中选出一组满足最长不下降子序列规则的机器人组成一 支精锐卫队。

所谓不下降子序列(Longest Increasing Subsequence,LIS)定义为:设有由$\red{n}$ 个不相同的整数组成的数列$\red{b[n],}$若有下标$\red{il<i2<}$$\red{...<iL}$且$\red{b[il]<b[i2]<}$$\red{...<b[iL],}$ 则称存在一个长度为$\red{L}$的不下降序列。 例如$\red{13,7,9,16,38,24.}$$\red{37,18}$$\red{.44,19,21,22 ,63,15}$。有$\red{13<16<38<44<63}$长度为$\red{5}$ 的不下降子序列。但经过观察,实际还有$\red{7<9<16<18<19<21<22<63}$长度为$\red{8}$的不下 降子序列。那么是不是还有更长的不下降子序列呢?请找出最长不下降子序列的长度。

输入格式

第一行为$\red{n,}$表示$\red{n(n≤}$$\red{100 000)}$个数。第二行为$\red{n}$个数的值。

输出格式

一个整数,即最长不下降序列的长度。

样例

输入样例

4
1 3 1 2

输出样例

2