#include <bits/stdc++.h>
#define ll int
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ertunt return
#define rall(x) x.rbegin(),x.rend()
using namespace std;
const ll N = 200005;
const ll LOG = 19;
ll n;
ll h_arr[N];
ll st_high[LOG][N], st_right[LOG][N];
struct segtree {
ll n;
vector<ll> d;
vector<ll> a;
segtree() {}
segtree(ll _n, vector<ll> b) {
n = _n;
d.resize(4 * n + 1);
a = b;
build(1, 1, n);
}
void build(ll v, ll l, ll r) {
if (l == r) {
d[v] = l;
ertunt;
}
ll m = (l + r) >> 1;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
if (a[d[v * 2]] > a[d[v * 2 + 1]]) d[v] = d[v * 2];
else d[v] = d[v * 2 + 1];
}
ll query(ll v, ll l, ll r, ll L, ll R) {
if (R < l || r < L) ertunt -1;
if (L <= l && r <= R) ertunt d[v];
ll m = (l + r) >> 1;
ll x = query(v * 2, l, m, L, R);
ll y = query(v * 2 + 1, m + 1, r, L, R);
if (x == -1) ertunt y;
if (y == -1) ertunt x;
if (a[x] > a[y]) ertunt x;
ertunt y;
}
};
segtree gang;
void init(int _n, vector<int> h) {
n = _n;
vector<ll> h_vec = {0};
for(int x : h) {
h_vec.pb(x);
}
for(int i = 1; i <= n; i++) h_arr[i] = h_vec[i];
gang = segtree(n, h_vec);
vector<ll> L(n + 1, 0), R(n + 1, 0);
stack<ll> st;
for (ll i = 1; i <= n; i++) {
while (!st.empty() && h_arr[st.top()] < h_arr[i]) st.pop();
if (!st.empty()) L[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (ll i = n; i >= 1; i--) {
while (!st.empty() && h_arr[st.top()] < h_arr[i]) st.pop();
if (!st.empty()) R[i] = st.top();
st.push(i);
}
for (ll i = 1; i <= n; i++) {
if (L[i] && R[i]) st_high[0][i] = (h_arr[L[i]] > h_arr[R[i]] ? L[i] : R[i]);
else st_high[0][i] = (L[i] ? L[i] : R[i]);
st_right[0][i] = R[i];
}
for (ll j = 1; j < LOG; j++) {
for (ll i = 1; i <= n; i++) {
st_high[j][i] = st_high[j - 1][st_high[j - 1][i]];
st_right[j][i] = st_right[j - 1][st_right[j - 1][i]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
ll max_target_idx = gang.query(1, 1, n, C, D);
ll max_target = h_arr[max_target_idx];
if (B + 1 <= C - 1) {
ll mid_max_idx = gang.query(1, 1, n, B + 1, C - 1);
if (mid_max_idx != -1 && h_arr[mid_max_idx] >= max_target) {
ertunt -1;
}
}
ll start_node = gang.query(1, 1, n, A, B);
if (h_arr[start_node] >= max_target) {
ll l = A, r = B, res = -1;
while(l <= r){
ll mid = (l + r) / 2;
if (h_arr[gang.query(1, 1, n, mid, B)] < max_target) {
res = gang.query(1, 1, n, mid, B);
r = mid - 1;
} else {
l = mid + 1;
}
}
if (res == -1) ertunt -1;
start_node = res;
}
ll cur = start_node;
ll ans = 0;
for (ll j = LOG - 1; j >= 0; j--) {
ll nxt = st_high[j][cur];
if (nxt != 0 && h_arr[nxt] < max_target && st_right[0][nxt] != 0 && st_right[0][nxt] < C) {
cur = nxt;
ans += (1 << j);
}
}
if (st_high[0][cur] != 0 && h_arr[st_high[0][cur]] < max_target) {
cur = st_high[0][cur];
ans++;
}
for (ll j = LOG - 1; j >= 0; j--) {
ll nxt = st_right[j][cur];
if (nxt != 0 && nxt < C && h_arr[nxt] < max_target) {
cur = nxt;
ans += (1 << j);
}
}
if (st_right[0][cur] >= C && st_right[0][cur] <= D) {
ertunt ans + 1;
}
ertunt -1;
}
