#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5 + 5;
const int LOG = 20;
int n;
vector<int> h;
vector<int> adj[MXN];
void init(int N, vector<int> H)
{
n = N, h = H;
int prv[N], nxt[N];
{
vector<int> st;
for (int i = 0; i < N; i++)
{
while (!st.empty() && H[i] > H[st.back()]) st.pop_back();
if (st.empty()) prv[i] = -1;
else prv[i] = st.back();
st.push_back(i);
}
}
{
vector<int> st;
for (int i = N - 1; i >= 0; i--)
{
while (!st.empty() && H[i] > H[st.back()]) st.pop_back();
if (st.empty()) nxt[i] = -1;
else nxt[i] = st.back();
st.push_back(i);
}
}
for (int i = 0; i < n; i++)
{
for (int j : {nxt[i], prv[i]})
{
if (j != -1) adj[i].push_back(j);
}
}
}
int minimum_jumps(int A, int B, int C, int D)
{
// A = max(A, B), C = min(C, D);
vector<int> d(n, -1);
queue<int> q;
for (int i = A; i <= B; i++) d[i] = 0, q.push(i);
while (!q.empty())
{
int a = q.front();
q.pop();
if (C <= a && a <= D) return d[a];
for (int &v : adj[a])
{
if (d[v] == -1)
{
d[v] = d[a] + 1;
q.push(v);
}
}
}
return -1;
}
