1237: 搬玩具

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:54 通过:18

题目描述

晫晫买了n 个玩具,每个玩具都放在纸箱里里没有拆封,纸箱编号为 1 到 n。第i个纸箱的高度,用一个正整数 ai 来表示。

现在晫晫要按照编号从小到大的顺序选出 m 个装着玩具的箱子从客厅搬到玩具房,要确保编号大的箱子比编号小的箱子高。

也就是对于任意的i<j 有 ai<aj,那么 m 最大可以是多少呢?

输入格式

第一行是正整数 n,表示 n 个箱子。

第二行 a1,a2…an 分别表示编号为 i 的箱子的高度。

输出格式

输出晫晫最多可以搬运的箱子个数。

数据范围

1≤n≤5000,
1≤ai≤10000

输入样例:

7
1 7 3 5 9 4 8

输出样例:

4

输入样例 复制

7
1 7 3 5 9 4 8

输出样例 复制

4