配点 : $300$ 点

問題文

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

制約

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

入力

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

$N$

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

出力

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

6
1 2 3 2 2 1

2

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

9
1 2 1 2 1 2 1 2 1

5

7
1 2 3 2 1 999999999 1000000000

3