题目描述

長さ $N$ の配列 $A$ が与えられます。 $A$ を何箇所かで切って、$A$ の連続した部分であるようないくつかの数列に分けます。 この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。 最小で何個の数列に分ければ良いかを求めて下さい。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

最小で何個の数列に分ければよいか出力せよ。

题目大意

题目翻译

给出长度为N的数列A，你需要把A划分成几个连续子串，要求每个子串都为单调不降子串或单调不升子串，求子串的最少个数。

输入输出格式

输入格式

第一行一个数N，第2行为数列A

输出格式

一个数，代表子串的最小个数

6
1 2 3 2 2 1

2

9
1 2 1 2 1 2 1 2 1

5

7
1 2 3 2 1 999999999 1000000000

3

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $A_i$ は全て整数である

Sample Explanation 1

$[1,2,3]$ と $[2,2,1]$ に分ければよいです。