题目描述

给定一串整数数列，将其划分为若干段连续的子序列，使得每段子序列内元素严格单调（递增或递减），且相邻段单调性不同。求出最少划分的子序列数目。

例如：数列 7,2,6,9,8,3,5,2,1 可以划分为 (7,2), (2,6,9), (9,8,3), (3,5), (5,2,1) 共 5 个子序列，答案为 5。其中 2,9,3,5 为转折元素。

输入格式

第一行，一个整数 $N$，表示数列长度。
第二行，$N$ 个整数，表示数列中的元素，保证任意两个相邻的数不相等。

输出格式

一个整数，表示划分出的子序列数目。

样例

5
1 3 5 4 6

3

样例解释
数列 1,3,5,4,6 可划分为 (1,3,5), (5,4), (4,6) 共 3 个子序列。

数据范围

• $2 \le N \le 10$
• 数列中元素均为整数，相邻元素互异。