#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n, L[200001], R[200001], d[200001];
bool subtask1, u[200001];
vector<int> g[200001];
void init(int N, std::vector<int> H) {
n = N;
stack<int> st;
subtask1 = 1;
for (int i = 0; i < N; i++) {
if (H[i] != i + 1) subtask1 = 0;
}
for (int i = 0; i < N; i++) {
while (st.size() && H[st.top()] <= H[i]) st.pop();
if (st.size()) L[i] = st.top();
else L[i] = -1;
st.push(i);
}
for (int i = N - 1; i >= 0; i--) {
while (st.size() && H[st.top()] <= H[i]) st.pop();
if (st.size()) R[i] = st.top();
else R[i] = -1;
st.push(i);
}
for (int i = 0; i < N; i++) {
if (L[i] != -1) g[i].push_back(L[i]);
if (R[i] != -1) g[i].push_back(R[i]);
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (subtask1) return C - B;
queue<int> q;
for (int i = 0; i < n; i++) u[i] = 0, d[i] = 0;
for (int i = A; i <= B; i++) {
u[i] = 1;
q.push(i);
}
while (q.size()) {
int x = q.front();
q.pop();
for (auto y : g[x]) {
if (!u[y]) {
u[y] = 1;
d[y] = d[x] + 1;
q.push(y);
}
}
}
//for (int i = 0; i < n; i++) cout << d[i] << " ";
//cout << "\n";
int ans = 1e9;
for (int i = C; i <= D; i++) if (u[i]) ans = min(ans, d[i]);
return (ans < 5e8 ? ans : -1);
}
