301001 - 最长不下降子序列

n个数组成的序列a[n],若有下标i_1<i_2<…<i_La[i_1]\leq a[i_2]\leq\cdots\leq a[i_L],则称存在一个长度为L的不下降序列。

例如13,7,9,16,38,24,37,18,44,19,21,22,63,15中,有13≤16≤38≤44≤63长度为5的不下降子序列。但经过观察,还有长度为8,即7\leq9\leq16\leq18\leq19\leq21\leq22\leq63的不下降子序列。

试编程求最长不下降子序列(longest increasing sequence,缩写为LIS)。

输入

第一行为n,表示n个数。

第二行为n个数的值。

输出

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

样例

输入

4
1 3 1 2

输出

3

提示

1≤n≤10^5

时间限制 1 秒
内存限制 128 MB
讨论 题解 统计
上一题 下一题