# CF1407D「Discrete Centrifugal Jumps」

## 1. 题目

### Description

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 < j$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $i < j$ and one of the following conditions satisfied:

• $i+1=j$

• $max(h_{i+1},…,h_{j-1})

• $max(h_i,h_j)

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.

### Input

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

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

### Output

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

### Note

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$.

## 2. 题解

### 分析

• 首先，要想明白这道题应该从何入手。这道题给人的第一感觉可能是 dp，却又不是简单的 dp。

• 进一步考虑，如何确定位置 $j$ 的 dp 值呢？跳到位置 $j$ 的上一个位置 $i$ 应该满足如下条件之一：

${\begin{array}{c} h_i \geq h_j , \quad \forall k \in (i,j), h_k \gt h_i \\ h_i \geq h_j , \quad \forall k \in (i,j), h_k \lt h_j \\ h_i \lt h_j , \quad \forall k \in (i,j), h_k \gt h_j \\ h_i \lt h_j , \quad \forall k \in (i,j), h_k \lt h_i \end{array}}$

• 从上一步考虑中我们可以看到单调栈的身影，单调栈正是用来求解序列中某个元素的首大于等于\小于等于的元素。定义单调栈的递增/递减是针对栈顶到栈底的元素大小的递增/递减，则
1. 对于条件

${\begin{array}{c} h_i \geq h_j , \quad \forall k \in (i,j), h_k \gt h_i \end{array}}$

1. 对于条件

${\begin{array}{c} h_i \geq h_j , \quad \forall k \in (i,j), h_k \lt h_j \end{array}}$

1. 对于条件

${\begin{array}{c} h_i \lt h_j , \quad \forall k \in (i,j), h_k \gt h_j \end{array}}$

1. 对于条件

${\begin{array}{c} h_i \lt h_j , \quad \forall k \in (i,j), h_k \lt h_i \end{array}}$

• 综上，就是记录每个元素左右的首大于等于/小于等于元素的位置。然后扫一遍这四个记录数组，对于存在右边首大于等于/小于等于元素的当前位置，应该将其加入到能够跳到对应位置的队列中去；对于存在左边首大于等于/小于等于元素的当前位置，应该将其左边首大于等于/小于等于元素的位置加入到能跳转到当前位置的队列中去。

• 如是，对于数组的每一个位置，都维护着一个能够跳到当前位置的上一个位置的队列。只需依次遍历这些队列，同时维护从最开始的位置跳到当前位置所需的最小步数即可。

【注】这道题主要需要考虑到的是如何得到能够跳到每一位置的上一个位置的集合。总的来说，这是道单调栈+dp的题。