题目描述

纽约有 $n$ 座漂亮的摩天大楼，其中第 $i$ 座的高度是 $h_i$ 。今天，一些恶棍放火烧毁了其中的 $n - 1$ 座摩天大楼，现在唯一安全的建筑就是第 $n$ 座摩天大楼了。

如果从第 $i$ 座摩天大楼跳到 第$j$ 座摩天大楼，那么它们之间的所有摩天大楼都严格低于或高于这两栋摩天大楼，那么我们就把这种跳转称为 离散。形式上，如果满足 $i<j$ 和以下条件之一，则跳转是离散的：

• $i + 1 = j$
• $\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})$ .

目前，瓦夏正待在第一座摩天大楼上，他想活得更久一点，所以他的目标是以最少的离散跳跃次数到达第 $n$ 座摩天大楼。帮他计算一下这个数字。

输入格式

第一行包含一个整数 $n$ ( $2 \le n \le 3 \cdot 10^5$ ) -摩天大楼总数。

第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$ ( $1 \le h_i \le 10^9$ )--摩天大楼的高度。

输出格式

打印单个数字 $k$ - 最小离散跳跃量。我们可以证明答案总是存在的。

5
1 3 1 4 5

3

4
4 2 2 4

1

2
1 1

1

5
100 1 100 1 100

2

提示

在第一个测试案例中，瓦夏可以通过以下方式跳转： $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ .

在第二和第三个测试案例中，我们可以一跳到达最后一幢摩天大楼。

第四个测试案例中的跳跃顺序： $1 \rightarrow 3 \rightarrow 5$ .