CF1407D.Discrete Centrifugal Jumps

There are $n$ beautiful skyscrapers in New York, the height of the $i$-th one is $h_i$. Today some villains have set on fire first $n - 1$ of them, and now the only safety building is $n$-th skyscraper.

Let's call a jump from $i$-th skyscraper to $j$-th ($i \lt j$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $i \lt j$ and one of the following conditions satisfied:

• $i + 1 = j$
• $\max(h_{i + 1}, \ldots, h_{j - 1}) \lt \min(h_i, h_j)$
• $\max(h_i, h_j) \lt \min(h_{i + 1}, \ldots, h_{j - 1})$.

At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach $n$-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.

纽约有 $n$ 座美丽的摩天大楼，第 $i$ 座的高度为 $h_i$。今天，一些反派纵火点燃了前 $n - 1$ 座大楼，目前唯一安全的大楼只剩下第 $n$ 座。

我们称从第 $i$ 座大楼跳到第 $j$ 座大楼（其中 $i \lt j$）是一次离散跳跃，当且仅当所有位于它们之间的大楼的高度严格低于二者中的较小值，或严格高于二者中的较大值。形式化地，跳跃是离散的，当且仅当 $i \lt j$ 且满足以下条件之一：

• $i + 1 = j$
• $\max(h_{i + 1}, \ldots, h_{j - 1}) \lt \min(h_i, h_j)$
• $\max(h_i, h_j) \lt \min(h_{i + 1}, \ldots, h_{j - 1})$。

此时，瓦西娅正站在第一座大楼上，他希望尽可能活得久一点，因此他的目标是以最少的离散跳跃次数到达第 $n$ 座大楼。请帮他计算这个最小跳跃次数。

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — total amount of skyscrapers.

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — heights of skyscrapers.

第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$）—— 摩天大楼的总数。

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

Print single number $k$ — minimal amount of discrete jumps. We can show that an answer always exists.

输出单个数字 $k$ —— 离散跳跃的最小次数。我们可以证明答案总是存在。

In the first testcase, Vasya can jump in the following way: $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: $1 \rightarrow 3 \rightarrow 5$.

在第一个测试用例中，瓦西娅可以按以下方式跳跃：$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$。

在第二和第三个测试用例中，我们可以通过一次跳跃到达最后一栋摩天大楼。

第四个测试用例中的跳跃序列：$1 \rightarrow 3 \rightarrow 5$。