导弹攻防战

题目描述

x国为了防御y国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它拦截的第一发炮弹可以是任意的高度，但是以后拦截的每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，告诉你这些来的导弹的高度，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

注意：导弹顺序是固定的。

输入格式

两行，第一行 $n$，表示有 $n$ 个导弹，其中 $1 \le n \le 500$。

接下来一行 $n$ 个整数，表示 $n$ 个导弹的高度，每个导弹的高度不超过 $30000$。

输出格式

输出一个 $k$，表示最少需要 $k$ 套这样的系统才能拦截所有的导弹。

样例输入 #1

6
389 207 300 200 310 65

样例输出 #1

3

数据范围

$1 \le n \le 500$，每个导弹的高度不超过 $30000$。

知识点与难度

本题涉及贪心基础与动态规划基础（最长上升子序列），从属于 GESP五级，难度等级：⭐⭐⭐。

测试点分布