#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 2e5 + 10;
vector<int> adj[mxn];
int dis[mxn];
void init(int N, vector<int> H) {
vector<int> L(N, -1), R(N, -1);
stack<int> st; st.push(0);
for(int i = 1; i < N; i++) {
while(st.size() && H[st.top()] <= H[i])
st.pop();
if(st.size())
L[i] = st.top();
st.push(i);
}
stack<int> en; en.push(0);
for(int i = N - 1; i >= 0; i--) {
while(en.size() && H[en.top()] <= H[i])
en.pop();
if(en.size())
R[i] = en.top();
en.push(i);
}
for(int i = 0; i < N; i++) {
if(L[i] > -1) adj[i].push_back(L[i]);
if(R[i] > -1) adj[i].push_back(R[i]);
}
}
int minimum_jumps(int A, int B, int C, int D) {
memset(dis, -1, sizeof dis);
priority_queue<pii> pq;
for(int i = A; i <= B; i++) {
pq.push(MP(0, i));
}
while(pq.size()) {
int d = -pq.top().ff;
int u = pq.top().ss;
pq.pop();
if(dis[u] > -1) continue;
dis[u] = d;
for(int v : adj[u])
if(dis[v] == -1)
pq.push(MP(-(d + 1), v));
}
int ans = INT_MAX;
for(int i = C; i <= D; i++)
if(dis[i] > -1)
ans = min(ans, dis[i]);
return (ans == INT_MAX) ? -1 : ans;
}
