离散离心跳跃

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $n$ 座依次排列的楼，第 $i$ 座楼的高度为 $h_i$。从第 $i$ 座楼跳到第 $j$ 座楼（$i<j$）是合法的，当且仅当满足下列条件之一：

• $j=i+1$；
• 中间所有楼都严格低于两端，即 $\max(h_{i+1},\ldots,h_{j-1})<\min(h_i,h_j)$；
• 中间所有楼都严格高于两端，即 $\max(h_i,h_j)<\min(h_{i+1},\ldots,h_{j-1})$。

求从第 $1$ 座楼到第 $n$ 座楼所需的最少跳跃次数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$。

输出格式

输出一个整数，表示最少跳跃次数。

样例输入 1

5
1 3 1 4 5

样例输出 1

3

样例输入 2

4
4 2 2 4

样例输出 2

1

样例输入 3

2
1 1

样例输出 3

1

样例输入 4

5
100 1 100 1 100

样例输出 4

2

数据范围

$2\le n\le 3\times 10^5$，$1\le h_i\le 10^9$。