[AGC013A] Sorted Arrays

## 题目翻译 给出长度为N的数列A，你需要把A划分成几个连续子串，要求每个子串都为单调不降子串或单调不升子串，求子串的最少个数。 ## 输入输出格式 ### 输入格式 第一行一个数N，第2行为数列A ### 输出格式 一个数，代表子串的最小个数

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

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

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] $ に分ければよいです。