#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
vector<pair<int, int>> st;
int n;
SegmentTree() { }
void init(const vector<int> &v) {
n = v.size();
st.resize(n << 1, {0, 0});
for (int i = 0; i < n; i++) {
st[i + n] = {v[i], i};
}
for (int i = n - 1; i > 0; i--) {
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
}
int qry(int l, int r) {
pair<int, int> mx = {0, 0};
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) mx = max(mx, st[l++]);
if (r & 1) mx = max(mx, st[--r]);
}
return mx.second;
}
} sgt;
const int N = 2e5, lg = 18, inf = 1e9;
int n, nxt[lg][N], prv[lg][N], g[lg][N], h[N];
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
sgt.init(H);
stack<int> st;
for (int i = 0; i < n; i++) {
while (st.size() && h[st.top()] <= h[i]) st.pop();
prv[0][i] = st.size() ? st.top() : -1;
st.push(i);
}
while (st.size()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (st.size() && h[st.top()] <= h[i]) st.pop();
nxt[0][i] = st.size() ? st.top() : -1;
st.push(i);
}
for (int i = 0; i < n; i++) {
if (nxt[0][i] == -1) g[0][i] = prv[0][i];
else if (prv[0][i] == -1) g[0][i] = nxt[0][i];
else g[0][i] = (h[nxt[0][i]] >= h[prv[0][i]] ? nxt[0][i] : prv[0][i]);
}
for (int i = 1; i < lg; i++) {
for (int j = 0; j < n; j++) {
prv[i][j] = prv[i - 1][j] == -1 ? -1 : prv[i - 1][prv[i - 1][j]];
nxt[i][j] = nxt[i - 1][j] == -1 ? -1 : nxt[i - 1][nxt[i - 1][j]];
g[i][j] = g[i - 1][j] == -1 ? -1 : g[i - 1][g[i - 1][j]];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
int mx = sgt.qry(c, d);
if (h[b] >= h[mx]) return -1;
for (int i = lg - 1; i >= 0; i--) {
if (prv[i][b] != -1 && prv[i][b] >= a && h[prv[i][b]] < h[mx]) {
b = prv[i][b];
}
}
if (c <= nxt[0][b] && nxt[0][b] <= d) return 1;
int e = sgt.qry(b + 1, c - 1);
if (h[e] >= h[mx]) return -1;
for (int i = lg - 1; i >= 0; i--) {
if (prv[i][a] != -1 && h[prv[i][a]] < h[e]) {
a = prv[i][a];
}
}
a = prv[0][a];
if (a != -1 && (h[a] < h[e] || h[a] >= h[mx])) a = -1;
int ans = 1, u = b;
for (int i = lg - 1; i >= 0; i--) {
if (g[i][b] != -1 && h[g[i][b]] <= h[e]) {
b = g[i][b];
ans += (1 << i);
}
}
for (int i = lg - 1; i >= 0; i--) {
if (nxt[i][b] != -1 && h[nxt[i][b]] <= h[e]) {
b = nxt[i][b];
ans += (1 << i);
}
}
if (a != -1) {
int ans2 = 1;
for (int i = lg - 1; i >= 0; i--) {
if (g[i][u] != -1 && h[g[i][u]] <= h[a]) {
u = g[i][u];
ans2 += (1 << i);
}
}
if (u == a) ans = min(ans, ans2);
}
return ans;
}
