#249. 最长不上升子序列长度 普及−

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

给定一个长度为 的序列 ),求一个最长的 的子序列,满足除第一个元素外,该子序列的每个元素都小于等于前一个元素。

  • 子序列:序列 子序列是从 中将若干元素提取出来并不改变相对位置形成的序列。空序列及原序列本身也是原序列的一个子序列。
  • 非空子序列:除了空序列之外的子序列。
  • 真子序列:除了原序列本身之外的子序列。
  • 非空真子序列:除了空序列及原序列本身之外的子序列。

输入格式

第一行一个数

第二行 个数

输出格式

一个整数,即最长上升子序列的长度。

样例

样例输入

7
4 2 3 7 6 5 8

样例输出

3

数据范围与提示

对于 的数据,