蹦一蹦

题目描述

小 w 为了长高他需要蹦一蹦，有 $n$ 个木桩排成一行，每个木桩有一个高度 $h_{i}$。 称可以从木桩 $i$ 跳到 木桩 $j$，当 $i, j (i<j )$ 满足以下三个条件之一：

$1.i+1=j$

$2.\max(h_{i+1},h_{i+2},\cdots,h_{j-1})<\min(h_i,h_j)$

$3.\min(h_{i+1},h_{i+2},\cdots,h_{j-1})>\max(h_i,h_j)$

现在小 w 在木桩 $1$，请求出跳到木桩 $n$ 最少要跳几次。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数表示木桩高度 $h_{i}$。

输出格式

输出一行最少跳跃次数。

样例 #1

样例输入 #1

5
1 3 1 4 5

样例输出 #1

3

样例 #2

样例输入 #2

4
4 2 2 4

样例输出 #2

1

样例 #3

样例输入 #3

2
1 1

样例输出 #3

1

样例 #4

样例输入 #4

5
100 1 100 1 100

样例输出 #4

2

提示

对于$30\%$ 的数据，满足 $1\le n \le 100$。

对于$50\%$ 的数据，满足 $1\le n \le 1000$。

对于$100\%$ 的数据，满足 $1\le n \le 3\times 10^5,1\le h_i \le 10^9$。