题目描述

某国研发出一种导弹拦截系统，但有一个缺陷：它拦截的第一发炮弹可以是任意高度，以后拦截的每一发炮弹都不能高于前一发的高度（即每套系统能拦截的高度序列必须单调不增）。雷达捕捉到敌国 $n$ 枚导弹来袭，按固定顺序给出它们的高度。最少需要配备多少套这样的系统，才能拦截所有导弹？

输入格式

第一行一个整数 $n$（$1 \le n \le 500$），表示导弹的数量。

第二行 $n$ 个整数，表示 $n$ 枚导弹的高度，每枚导弹的高度不超过 $30000$。

输出格式

一行，一个整数 $k$，表示最少需要 $k$ 套拦截系统。

样例

6
389 207 300 200 310 65

3

说明/提示

贪心策略：处理每一枚导弹时，从已有的拦截系统中，选择当前拦截高度最低、且不小于该导弹高度的那一套来拦截（并更新该系统的拦截高度为导弹高度）；如果现有所有系统都无法拦截（高度都低于导弹），则新增一套系统。