题目描述

To play against the threats of malicious countries nearby, Country R has updated their missile defence system. The new type system can bring down a series of missiles as long as they are coming in ascending order by altitude or descending order by altitude.

Given the heights of a sequence of coming missiles, the general wants to know how many sets of the new type systems are needed to bring down all of them.

输入格式

The input consists of several test cases. The first line of each test case contains an integer $n (1 \le n \le 50)$. The next line contains n different integers indicating the heights.

输出格式

For each test case output a single line containing the number of systems needed.For each test case output a single line containing the number of systems needed.

题目大意

题目描述

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

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

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

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

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 $n$，表示来袭导弹数量。

第二行包含 $n$ 个不同的整数，表示每个导弹的高度。

当输入测试用例 $n=0$ 时，表示输入终止，且该用例无需处理。

输出格式

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

说明与提示

样例解释

对于样例，需要两套系统。一套击落 $3,4$ 号导弹，另一套击落 $5,2,1$ 号导弹。

数据规模与约定

$1 \leq n \leq 50$。

5 
3 5 2 4 1 
0

2

提示

Two sets of systems are needed for the sample. One brings down 3, 4 and the other brings down 5, 2, 1.