#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a,b,c,d) for(int a = b;a <= c; a += d)
#define repl(a,b,c,d) for(int a = b; a >= c; a -= d)
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
const int LG = 19;
const int N = 2e5 + 5;
int lg[N];
int upb[N][LG]; // Higher jump
int ups[N][LG]; // Strictly right jump
int nxt[N];
int lst[N];
int tv[N];
int n;
void prec() {
lg[1] = 0;
rep(i, 2, N - 1, 1)
lg[i] = lg[i >> 1] + 1;
}
struct sparse {
V<int> arr;
V<V<int>> mn;
V<V<int>> mx;
int n, l;
int comparemn(int a, int b) {
if (arr[a] <= arr[b]) return a;
return b;
}
int comparemx(int a, int b) {
if (arr[a] >= arr[b]) return a;
return b;
}
void init(int nn, V<int> a) {
n = nn;
l = lg[n] + 1;
arr = a;
mn.resize(n + 1, V<int>(l + 1));
mx.resize(n + 1, V<int>(l + 1));
rep(i, 1, n, 1) {
mn[i][0] = i;
mx[i][0] = i;
}
rep(j, 1, l, 1) {
rep(i, 1, n, 1) {
if (i + (1 << (j - 1)) <= n) {
mn[i][j] = comparemn(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
mx[i][j] = comparemx(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
} else {
mn[i][j] = mn[i][j - 1];
mx[i][j] = mx[i][j - 1];
}
}
}
}
int range_min(int l, int r) {
if (l > r) return 0;
int d = r - l + 1;
int log = lg[d];
return comparemn(mn[l][log], mn[r - (1 << log) + 1][log]);
}
int range_max(int l, int r) {
if (l > r) return 0;
int d = r - l + 1;
int log = lg[d];
return comparemx(mx[l][log], mx[r - (1 << log) + 1][log]);
}
} rmq;
void init(int nn, vector<int> H) {
n = nn;
prec();
rep(i, 1, n, 1) {
tv[i] = H[i - 1];
}
V<int> a(n + 1);
rep(i, 0, n, 1) {
a[i] = tv[i];
}
rmq.init(n, a);
stack<int> st;
st.push(1);
rep(i, 2, n, 1) {
while (!st.empty() && a[st.top()] < a[i]) {
nxt[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
nxt[st.top()] = 0; // Using 0 as a safe null state
st.pop();
}
st.push(n);
repl(i, n - 1, 1, 1) {
while (!st.empty() && a[st.top()] < a[i]) {
lst[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
lst[st.top()] = 0;
st.pop();
}
auto valid = [&](int x) {
return (1 <= x && x <= n);
};
auto compareb = [&](int i) {
int a = nxt[i];
int b = lst[i];
int val_a = valid(a) ? tv[a] : -1;
int val_b = valid(b) ? tv[b] : -1;
if (val_a == -1 && val_b == -1) return 0;
if (val_a > val_b) return a;
return b;
};
auto compares = [&](int i) {
// Strict right jump for the fallback!
if (valid(nxt[i])) return nxt[i];
return 0;
};
rep(i, 1, n, 1) {
upb[i][0] = compareb(i);
ups[i][0] = compares(i);
}
int l = lg[n] + 1;
rep (j, 1, l, 1) {
rep(i, 1, n, 1) {
upb[i][j] = upb[upb[i][j - 1]][j - 1];
ups[i][j] = ups[ups[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
++A; ++B; ++C; ++D;
int M = rmq.range_max(C, D);
int mx_C = tv[M];
int mid_max = 0;
if (B + 1 <= C - 1) {
mid_max = tv[rmq.range_max(B + 1, C - 1)];
}
// Impossible to cross the gap
if (mid_max > mx_C) return -1;
// Binary search for the first element looking left from B that is taller than mx_C
int l = A, r = B, X = A - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (tv[rmq.range_max(mid, B)] > mx_C) {
X = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// If B itself (or everything up to B) is taller than mx_C, we can't start safely
if (X == B) return -1;
// Our starting position is the tallest safe tree in [X+1, B]
int pos = rmq.range_max(X + 1, B);
// If we start taller than the gap, it takes exactly 1 jump into C..D
if (tv[pos] > mid_max) return 1;
int jumps = 0;
int log = lg[n] + 1;
// 1. Lift using upb (High Jumps) as long as we don't overshoot mx_C
// AND as long as upb doesn't land us in a spot where we can cross mid_max in 1 jump.
repl(i, log, 0, 1) {
int nxt_node = upb[pos][i];
if (nxt_node != 0 && tv[nxt_node] < mx_C && tv[ups[nxt_node][0]] <= mid_max) {
pos = nxt_node;
jumps += (1 << i);
}
}
// Check if one final High Jump puts us directly in position to cross
int nxt_node = upb[pos][0];
if (nxt_node != 0 && tv[nxt_node] < mx_C) {
return jumps + 2;
}
// 2. Otherwise fall back to ups (Right Jumps) to inch forward over the mid_max
repl(i, log, 0, 1) {
nxt_node = ups[pos][i];
if (nxt_node != 0 && tv[nxt_node] <= mid_max) {
pos = nxt_node;
jumps += (1 << i);
}
}
return jumps + 1;
}
