1. 题目

题目链接：CF1407D「Discrete Centrifugal Jumps」 。

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}) < \min(h_i,h_j)$

• $\max(h_i,h_j) < \min(h_{i+1},…,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 calculating 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.

Examples

Input #1

5
1 3 1 4 5

Output #1

3

Input #2

4
4 2 2 4

Output #2

1

Input #3

2
1 1

Output #3

1

Input #4

5
100 1 100 1 100

Output #4

2

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. 题解

分析

做这道题的时候，蒟蒻的我也是毫无头绪，看完官方题解还琢磨了半天才明白（菜。。。Orz）。

• 首先，要想明白这道题应该从何入手。这道题给人的第一感觉可能是 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}$$

定义 $h_i$ 右边的首小于等于元素为 $h_j$，此时应该用非严格单调递减栈从右往左扫描序列，记录每个位置 $i$ 右边的首小于等于元素的位置 $j$。
2. 对于条件

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

定义 $h_j$ 左边的首大于等于元素为 $h_i$，此时应该用非严格单调递增栈从左往右扫描序列，记录每个位置 $j$ 左边的首大于等于元素的位置 $i$。
3. 对于条件

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

定义 $h_j$ 左边的首小于元素为 $h_i$，为了便于处理，我们可以看作 $h_j$ 左边的首小于等于元素为 $h_i$（不然需要特判 $h_j = h_i$ 的情况：若 $h_i = h_j$，那么 $h_j$ 没有左边首小于元素；而多记录一次（前两条条件已经记录了一次）可能跳转到 $j$ 的 $i$ 位置并不影响最终求解），此时应该用非严格单调递减栈从左往右扫描序列，记录每个位置 $j$ 左边的首小于等于元素的位置 $i$。
4. 对于条件

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

定义 $h_i$ 右边的首大于元素为 $h_j$，为了便于处理，我们可以看作 $h_i$ 右边的首大于等于元素为 $h_j$（不然需要特判 $h_j = h_i$ 的情况：若 $h_i = h_j$，那么 $h_i$ 没有右边首大于元素；而多记录一次（前两条条件已经记录了一次）可能跳转到 $j$ 的 $i$ 位置并不影响最终求解），此时应该用非严格单调递减栈从右往左扫描序列，记录每个位置 $i$ 右边的首大于等于元素的位置 $j$。

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

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

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

代码

#include <bits/stdc++.h>
#define ll int 
#define MAXN 300005
#define INF 0x3f3f3f3f
using namespace std;

ll n;
ll i, cnt;
ll h[MAXN];
ll dp[MAXN];
ll lle[MAXN], lge[MAXN], rle[MAXN], rge[MAXN];
vector <ll> jump[MAXN];
vector < pair<ll,ll> > stk;

int main()
{
    scanf("%d", &n);
    for(ll i = 0; i < n; ++i) {
        scanf("%d", h+i);
    }
    // 计算所有结点左边首小于等于的结点
    i = 0;
    lle[i] = -1;
    stk.clear();
    stk.push_back(pair<ll,ll>{i,h[i]});
    while(++i < n) {
        while(stk.size() && stk.back().second > h[i]) {
            stk.pop_back();
        }
        if(stk.size())  lle[i] = stk.back().first;
        else    lle[i] = -1;
        stk.push_back(pair<ll,ll>{i,h[i]});
    }
    // 计算所有结点左边首大于等于的结点
    i = 0;
    lge[i] = -1;
    stk.clear();
    stk.push_back(pair<ll,ll>{i,h[i]});
    while(++i < n) {
        while(stk.size() && stk.back().second < h[i]) {
            stk.pop_back();
        }
        if(stk.size())  lge[i] = stk.back().first;
        else    lge[i] = -1;
        stk.push_back(pair<ll,ll>{i,h[i]});
    }
    // 计算所有结点右边首小于等于的结点
    i = n-1;
    rle[i] = -1;
    stk.clear();
    stk.push_back(pair<ll,ll>{i,h[i]});
    while(~(--i)) {
        while(stk.size() && stk.back().second > h[i]) {
            stk.pop_back();
        }
        if(stk.size())  rle[i] = stk.back().first;
        else    rle[i] = -1;
        stk.push_back(pair<ll,ll>{i,h[i]});
    }
    // 计算所有结点右边首大于等于的结点
    i = n-1;
    rge[i] = -1;
    stk.clear();
    stk.push_back(pair<ll,ll>{i,h[i]});
    while(~(--i)) {
        while(stk.size() && stk.back().second < h[i]) {
            stk.pop_back();
        }
        if(stk.size())  rge[i] = stk.back().first;
        else    rge[i] = -1;
        stk.push_back(pair<ll,ll>{i,h[i]});
    }
    // 计算每个结点所有前面可能跳过来的结点
    for(ll i = 0; i < n; ++i) {
        if(lle[i] != -1)    jump[i].push_back(lle[i]);
        if(lge[i] != -1)    jump[i].push_back(lge[i]);
        if(rle[i] != -1)    jump[rle[i]].push_back(i);
        if(rge[i] != -1)    jump[rge[i]].push_back(i);
    }
    // 计算 dp
    dp[0] = 0;
    for(ll i = 1; i < n; ++i) {
        dp[i] = INF;
        for(auto to : jump[i]) {
            dp[i] = min(dp[i], dp[to]+1);
        }
    }
    printf("%d\n", dp[n-1]);
    return 0;
}