#include "jumps.h"
#include <bits/stdc++.h>
#define emb emplace_back
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
int n, a[N], l[N], r[N];
vector <int> adj[N];
void init(int nn, std::vector<int> h) {
n = nn;
for (int i = 0; i < n; i++) a[i + 1] = h[i];
stack <pii> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && st.top().first < a[i]) st.pop();
if (!st.empty()) l[i] = st.top().second;
st.emplace(a[i], i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && st.top().first < a[i]) st.pop();
if (!st.empty()) r[i] = st.top().second;
st.emplace(a[i], i);
}
while (!st.empty()) st.pop();
for (int i = 1; i <= n; i++) {
if (l[i]) adj[i].emb(l[i]);
if (r[i]) adj[i].emb(r[i]);
// cout << i << " : ";
// if (l[i]) cout << l[i] << " ";
// if (r[i]) cout << r[i] << " ";
// cout << "\n";
}
}
int minimum_jumps(int l1, int r1, int l2, int r2) {
l1++, r1++, l2++, r2++;
queue <pii> q;
vector <int> dis(n + 1, inf);
for (int i = l1; i <= r1; i++) q.emplace(0, i), dis[i] = 0;
while (!q.empty()) {
auto [w, u] = q.front(); q.pop();
// cout << u << " : " << w << "\n";
for (auto v : adj[u]) {
int nw = w + 1;
if (nw >= dis[v]) continue;
dis[v] = nw;
q.emplace(dis[v], v);
if (v >= l2 && v <= r2) return dis[v];
}
}
return -1;
}
