导弹防御系统

题目描述

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

防御系统特性

一套防御系统的导弹拦截高度要么一直严格单调上升，要么一直严格单调下降。

例如：

• 如果一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。
• 如果一套系统先后拦截了高度为 5 和高度为 2 的两发导弹，那么接下来该系统就只能拦截高度小于 2 的导弹。

问题

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例：

• 第一行包含整数 n，表示来袭导弹数量
• 第二行包含 n 个不同的整数，表示每个导弹的高度
• 当输入测试用例 n=0 时，表示输入终止，且该用例无需处理

输出格式

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围

$1 \le n \le 50$

输入样例

5
3 5 2 4 1
0

输出样例

2

样例解释

来袭导弹高度：[3, 5, 2, 4, 1]

最少需要两套防御系统：

1. 第一套系统：采用上升序列，拦截高度为 3, 4 的导弹

   • 先拦截高度 3
   • 然后拦截高度 4（4 > 3，满足严格单调上升）

2. 第二套系统：采用下降序列，拦截高度为 5, 2, 1 的导弹

   • 先拦截高度 5
   • 然后拦截高度 2（2 < 5，满足严格单调下降）
   • 最后拦截高度 1（1 < 2，满足严格单调下降）

这样，所有 5 发导弹都被击落，共使用 2 套防御系统。

关键点

1. 导弹高度各不相同：题目明确说明 n 个不同的整数
2. 系统类型选择自由：对于每套防御系统，我们可以自由选择让它采用上升序列还是下降序列
3. 拦截顺序固定：导弹来袭顺序是固定的，必须按输入顺序拦截
4. 最少系统数量：目标是使用尽可能少的防御系统拦截所有导弹
5. 系统独立工作：每个系统独立拦截导弹，互不干扰

问题等价转换

这个问题等价于：

• 将给定的导弹序列划分为若干个子序列
• 每个子序列要么是严格单调递增的，要么是严格单调递减的
• 求最少需要多少个子序列

这是一个导弹拦截系统的扩展问题，普通导弹拦截问题只能使用单调下降序列，而此题允许选择单调上升或单调下降。

时空限制

• 时间限制：1秒
• 空间限制：64MB