#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MxN = 2e5 + 5;
int n, l[MxN], r[MxN];
vector<int> h, v[MxN];
vector<pii> c;
bool sub1 = 1;
void init(int N, std::vector<int> H) {
n = N; h = H;
stack<int> st;
for (int i = 0; i < n; i++) {
if (h[i] != i + 1) sub1 = 0;
c.emplace_back(h[i], i);
}
sort(c.begin(), c.end());
for (int i = 0; i < n; i++) {
l[i] = -1;
while (!st.empty() && h[i] > h[st.top()]) st.pop();
if (!st.empty()) l[i] = st.top();
st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
r[i] = -1;
while (!st.empty() && h[i] > h[st.top()]) st.pop();
if (!st.empty()) r[i] = st.top();
st.emplace(i);
}
for (int i = 0; i < n; i++) {
if (~l[i]) v[l[i]].emplace_back(i);
if (~r[i]) v[r[i]].emplace_back(i);
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (sub1) return C - B;
vector<int> dp(n + 5, 1e9);
for (int i = A; i <= B; i++) dp[i] = 0;
for (auto &[x, y]: c) {
for (auto &e: v[y]) dp[y] = min(dp[y], dp[e] + 1);
}
int ans = 1e9;
for (int i = C; i <= D; i++) ans = min(ans, dp[i]);
return (ans == 1e9 ? -1 : ans);
}
