#1517. 深空采样

    ID: 1517 传统题 文件IO:six 1000ms 256MiB 尝试: 19 已通过: 0 难度: 普及+/提高− 上传者: 标签>二分贪心数据结构树状数组

深空采样

本题需要文件读写

文件 IO 为:输入文件 six.in,输出文件 six.out。请使用上述文件名读入和输出。

问题描述

有 NN 颗陨石,按记录顺序给出它们的质量。你可以按该顺序挑选若干颗陨石装入样本舱,也可以跳过某些陨石。

所选陨石的质量必须严格递减,即每颗新装入陨石的质量必须小于上一颗已装入陨石的质量。请计算最多能够装入多少颗陨石。

输入格式

从文件 six.in 中读入数据。

第一行输入一个整数 NN,表示陨石总数。

接下来 NN 行,每行输入一个整数,依次表示每颗陨石的质量。

输出格式

输出到文件 six.out。

输出一行一个整数,表示最多可以装入的陨石数量。

样例输入 1

9
7
10
7
8
9
7
8
6
4

样例输出 1

5

样例输入 2

4
5
5
5
5

样例输出 2

1

评测数据规模

对于所有数据,保证 1≤N≤2×1051\leq N\leq2\times10^5,每颗陨石的质量在 11 到 2×1052\times10^5 之间。