No testdata at current.

题目描述

给定一个长度为$n$的数列$A$，要求划分最少的段数，使得每一段要么单调不降，要么单调不升。

输入格式

第一行一个整数$n$。

接下来 个数表示数列$A$。

输出格式

输出最少的划分数。

样例

样例输入 1

6
1 2 3 2 2 1

样例输出 1

2

样例输入 2

9
1 2 1 2 1 2 1 2 1

样例输出 2

5

样例输入 3

7
1 2 3 2 1 999999999 1000000000

样例输出 3

3

数据范围与提示

对于$30\%$的数据, $1\leq n \leq 10$；

对于$60\%$的数据，$1\leq1000$；

对于$80\%$的数据，保证数据随机生成；

对于$100\%$的数据，$1\leq n \leq100000$, $a_i$在 int 范围内。