#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }
int n;
vector<int> h;
vector<vector<int>> adj;
void init(int N, std::vector<int> H) {
n = N;
h = H;
adj.resize(n);
// map<int, int> id;
// vector<int> dup = h;
// sort(all(dup));
// int cnt = 0;
// for (int i = 0; i < n; i++) id[dup[i]] = cnt++;
// for (int i = 0; i < n; i++) h[i] = id[h[i]];
stack<int> st;
for (int i = 0; i < n; i++) {
// cout << st.size() << endl;
while (st.size() > 0 && h[st.top()] < h[i]) {
st.pop();
}
if (st.size() != 0) adj[i].push_back(st.top());
st.push(i);
}
while (st.size() != 0) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (st.size() > 0 && h[st.top()] < h[i]) {
st.pop();
}
if (st.size() != 0) adj[i].push_back(st.top());
st.push(i);
}
}
int minimum_jumps(int a, int b, int c, int d) {
int res = 1e6;
queue<pair<int, int>> nodes;
for (int start = a; start <= b; start++) {
nodes.emplace(start, 0);
}
vector<bool> vis(n, 0);
// cout << pl(adj[4]) << endl;
while (nodes.size() > 0) {
auto [cur_node, dist] = nodes.front();
nodes.pop();
if (vis[cur_node]) continue;
vis[cur_node] = 1;
// cout << pl(cur_node) << pl(dist) << endl;
if (c <= cur_node && cur_node <= d) {
res = min(res, dist);
break;
}
for (int v : adj[cur_node]) {
nodes.emplace(v, dist + 1);
}
}
if (res == 1e6) return -1;
return res;
}
