CF1407D Discrete Centrifugal Jumps

纽约有 $n$ 座美丽的摩天大楼，第 $i$ 座的高度为 $h_i$。今天，一些恶棍点燃了前 $n-1$ 座大楼，现在唯一安全的大楼是第 $n$ 座。 我们称从第 $i$ 座大楼跳到第 $j$ 座大楼（$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})$ 此刻，Vasya 正站在第一座大楼上，他想多活一会儿，所以他的目标是用最少的离散跳跃次数到达第 $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$，表示最小的离散跳跃次数。可以保证一定存在解。

在第一个样例中，Vasya 可以按如下方式跳跃：$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$。 在第二个和第三个样例中，可以一次跳跃到达最后一座大楼。 第四个样例的跳跃序列为：$1 \rightarrow 3 \rightarrow 5$。 由 ChatGPT 4.1 翻译