题目描述

给定一个长度为 $N$ 的数组 $A$。你的任务是将它分成多个连续子数组。这里，所有得到的子数组必须按照非递减或非递增的顺序进行排序。你至少需要将 $A$ 分成多少个子数组？

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 每个 $A_i$ 都是整数。

输入

从标准输入读入输入数据，具体格式如下：

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

输出 $A$ 分割后可能的最小子数组数。

示例输入 1

6
1 2 3 2 2 1

示例输出 1

2

一个最优解是将数组分成 \[1,2,3\] 和 \[2,2,1\]。

示例输入 2

9
1 2 1 2 1 2 1 2 1

示例输出 2

5

示例输入 3

7
1 2 3 2 1 999999999 1000000000

示例输出 3

3