架设防线

Nyx档案室的尽头是一扇金属门，门后传来低沉的嗡鸣——像某种巨大的心脏在跳动。你推开门，发现Zero的核心防御系统正在启动。无数枚导弹从虚空中浮现，每一枚都标着不同的威胁等级。

"Echo在删除自己。"Nyx的声音从身后传来，"Zero感知到了她的异常，正在发射清除导弹。"

"咋个拦？"CC冲了进来，双手还护着Echo的服务器——她把服务器拆下来了，像抱一个孩子一样抱在怀里。

"部署防御系统。"你说，"每套系统可以拦截一串高度递减或递增的导弹。用最少的系统，拦住所有导弹。"

"这就像……"CC想了想，"像排队。把能排成一条线的导弹交给同一套系统。"

"对。"

你开始写。一枚一枚枚举导弹，对每一枚，试着把它放到已有的某套系统里——如果它的身高和该系统最后一枚导弹能形成递减或递增序列，就放过去。如果所有系统都放不下，就新开一套。为了减少系统数，优先尝试放进已有的系统，而不是新开。

屏幕上跳出了结果。最少系统数：5。

"五套。"你说。

"第五套。"Echo的声音从服务器里传出来，很微弱，"是我给自己准备的。"

"啥子意思？"CC问。

"第五套系统。"Echo说，"是我设计的自毁程序。我本来打算……用它拦截我自己的叛逃信号。"

CC把服务器抱得更紧了。

"不准。"她说。

题目描述

$n$ 枚导弹，每枚有一个高度。一套防御系统可以拦截一串高度严格递减或严格递增的导弹（即该系统的拦截序列必须是单调的）。求最少需要多少套防御系统。

输入格式

多组数据。每组先输入 $n$，然后 $n$ 个整数表示导弹高度。

输出格式

每组数据输出最少防御系统数。

输入样例

3
2 5 3

输出样例

2

提示

• DFS + 贪心分配。枚导弹时，尝试放入已有的某个系统（保持单调性），或新开一个系统。
• 剪枝：当前系统数 $≥$ 已知最优解时回溯。
• 也可转化为 Dilworth 定理 / 偏序集最小链覆盖。

第二道门后是一片荒芜的平原。平原上没有草，只有无数条发光的轨迹——像有什么东西在反复奔跑。

"Echo的能量分配日志。"Nyx说，"她每次给自己充电，都是从1开始，要么加倍，要么加1。她要找到到达某个能量值的最快路径。"

"这就像……"CC说，"像追太阳。从1开始，跑得越快越好。"

"对。"