#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
using pi = pair<int, int>;
class MST {
public:
int n;
V<int> h, tree;
MST() {}
MST(const V<int>& h) {
this->h = h;
n = h.size();
tree = V<int>(4 * n);
build(0, n - 1, 0);
}
void build(int l, int r, int idx) {
if (l == r) {
tree[idx] = r;
return;
}
int m = (l + r) / 2;
build(l, m, 2 * idx + 1);
build(m + 1, r, 2 * idx + 2);
int il = tree[2 * idx + 1],
ir = tree[2 * idx + 2];
tree[idx] = h[il] > h[ir] ? il : ir;
}
int query(int l, int r, int idx, int ql, int qr) {
if (l > qr || r < ql) return -1;
if (ql <= l && r <= qr) return tree[idx];
int m = (l + r) / 2;
int il = query(l, m, 2 * idx + 1, ql, qr),
ir = query(m + 1, r, 2 * idx + 2, ql, qr);
if (il == -1) return ir;
if (ir == -1) return il;
return h[il] > h[ir] ? il : ir;
}
};
const int INF = 1e9+7;
int n, q, root;
V<int> h;
V<pi> iv; // i can be only be accessed from [l, r]
V<V<int>> ch, fa;
MST mst;
void dfs(int l, int r, int i) {
iv[i] = {l, r};
if (i > l) {
int ni = mst.query(0, n - 1, 0, l, i - 1);
ch[i][0] = ni;
dfs(l, i - 1, ni);
}
if (i < r) {
int ni = mst.query(0, n - 1, 0, i + 1, r);
ch[i][1] = ni;
dfs(i + 1, r, ni);
}
}
void init(int N, int H[]) {
n = N;
h.resize(n);
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
mst = MST(h);
root = mst.query(0, n - 1, 0, 0, n - 1);
ch = V<V<int>>(n, V<int>(2, -1));
iv = V<pi>(n);
dfs(0, n - 1, root);
V<int> st;
st = {};
fa = V<V<int>>(n, V<int>(2, -1));
for (int i = 0; i < n; i++) {
while (st.size() && h[st.back()] < h[i]) st.pop_back();
fa[i][0] = (st.size() ? st.back() : -1);
st.push_back(i);
}
st = {};
for (int i = n - 1; i >= 0; i--) {
while (st.size() && h[st.back()] < h[i]) st.pop_back();
fa[i][1] = (st.size() ? st.back() : -1);
st.push_back(i);
}
}
int minimum_jumps(int A, int B, int C, int D) {
V<int> d(n, -1);
queue<pi> q;
for (int i = A; i <= B; i++) {
q.push({i, 0});
}
while (!q.empty()) {
pi x = q.front();
q.pop();
if (x.first == -1) continue;
if (d[x.first] != -1) continue;
d[x.first] = x.second;
q.push({fa[x.first][0], x.second + 1});
q.push({fa[x.first][1], x.second + 1});
}
int ans = INF;
for (int i = C; i <= D; i++) {
if (d[i] != -1) {
ans = min(ans, d[i]);
}
}
return (ans == INF ? -1 : ans);
}
