#include "jumps.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int INF = 1e9 + 7;
const int N = 2e5 + 5;
int h[N];
int n;
int dp[N];
vector<int> g[N];
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; ++ i) {
h[i] = H[i - 1];
}
stack<int> st;
for (int i = 1; i <= n; ++ i) {
while (!st.empty() and h[st.top()] < h[i]) st.pop();
if (!st.empty()) g[i].pb(st.top());
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n; i; -- i) {
while (!st.empty() and h[st.top()] < h[i]) st.pop();
if (!st.empty()) g[i].pb(st.top());
st.push(i);
}
}
int minimum_jumps(int a, int b, int c, int d) {
a += 1, b += 1, c += 1, d += 1;
fill(dp + 1, dp + n + 1, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = a; i <= b; ++ i) {
pq.push({0, i});
}
while (!pq.empty()) {
auto [k, nd] = pq.top(); pq.pop();
if (dp[nd] <= k) continue;
dp[nd] = k;
k += 1;
for (auto it : g[nd]) {
if (dp[it] > k) {
pq.push({k, it});
}
}
}
int ans = INF;
for (int i = c; i <= d; ++ i) ans = min(ans, dp[i]);
if (ans >= INF) ans = -1;
return ans;
}
/*
k nd
*/
