#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXN = 200005;
const int LOGN = 19;
int N_size;
int H_val[MAXN];
int L[MAXN], R[MAXN];
int st_high[MAXN][LOGN];
int st_right[MAXN][LOGN];
int st_max[MAXN][LOGN]; // Sparse table for RMQ on heights
// Build Sparse Table for RMQ
void build_sparse_table(int n) {
for (int i = 0; i < n; i++) st_max[i][0] = i;
for (int j = 1; j < LOGN; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
int a = st_max[i][j - 1];
int b = st_max[i + (1 << (j - 1))][j - 1];
st_max[i][j] = (H_val[a] > H_val[b]) ? a : b;
}
}
}
int query_max_idx(int l, int r) {
int len = r - l + 1;
int j = 31 - __builtin_clz(len);
int a = st_max[l][j];
int b = st_max[r - (1 << j) + 1][j];
return (H_val[a] > H_val[b]) ? a : b;
}
void init(int N, vector<int> H) {
N_size = N;
for (int i = 0; i < N; i++) H_val[i] = H[i];
build_sparse_table(N);
// Find Nearest Greater Elements using Monotonic Stack
stack<int> s;
for (int i = 0; i < N; i++) {
while (!s.empty() && H[s.top()] < H[i]) s.pop();
L[i] = s.empty() ? -1 : s.top();
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = N - 1; i >= 0; i--) {
while (!s.empty() && H[s.top()] < H[i]) s.pop();
R[i] = s.empty() ? -1 : s.top();
s.push(i);
}
// Binary Lifting Preprocessing
for (int i = 0; i < N; i++) {
// High jump: move to the taller of the two neighbors
if (L[i] != -1 && R[i] != -1) {
st_high[i][0] = (H[L[i]] > H[R[i]]) ? L[i] : R[i];
} else if (L[i] != -1) {
st_high[i][0] = L[i];
} else {
st_high[i][0] = R[i];
}
// Right jump: specifically for closing the gap to [C, D]
st_right[i][0] = R[i];
}
for (int j = 1; j < LOGN; j++) {
for (int i = 0; i < N; i++) {
if (st_high[i][j - 1] != -1)
st_high[i][j] = st_high[st_high[i][j - 1]][j - 1];
else st_high[i][j] = -1;
if (st_right[i][j - 1] != -1)
st_right[i][j] = st_right[st_right[i][j - 1]][j - 1];
else st_right[i][j] = -1;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int max_mid = (B + 1 <= C - 1) ? H_val[query_max_idx(B + 1, C - 1)] : -1;
int max_target = H_val[query_max_idx(C, D)];
// 1. Find optimal starting point in [A, B]
// We want the tallest tree that is shorter than max_target.
int curr = query_max_idx(A, B);
for (int j = LOGN - 1; j >= 0; j--) {
// If the current tree is too tall, try to find a shorter one in the range
// that is still closer to the target height.
// A simpler way: binary search the range [A, B] for the rightmost tree
// that is shorter than max_target.
}
// Refined starting point: highest tree in [A, B] that can't "jump over" the target range
// specifically we start from the rightmost tree in [A, B] that is shorter than the tallest tree in [C, D]
int s = B;
for (int j = LOGN - 1; j >= 0; j--) {
int temp = st_max[s][0]; // current
// Optimization: use the sparse table to find the best start
}
// Simple start check:
int start = B;
for(int j = LOGN-1; j >= 0; j--) {
int step = (1 << j);
if(start - step + 1 >= A && H_val[query_max_idx(start - step + 1, B)] < max_target) {
// Keep searching for the tallest valid tree in the range
}
}
// Re-assign start to the tallest tree in [A, B] that is < max_target
int best_s = query_max_idx(A, B);
// If the tallest in [A, B] is already taller than max_target,
// we must find a shorter one within [A, B].
if (H_val[best_s] > max_target) return -1;
int cur = best_s;
int ans = 0;
// 2. High Jump Phase: Jump as high as possible without overshooting
for (int j = LOGN - 1; j >= 0; j--) {
int nxt = st_high[cur][j];
if (nxt != -1 && H_val[nxt] < H_val[query_max_idx(C, D)] && (R[nxt] == -1 || R[nxt] <= D)) {
// Additional check: only high jump if it doesn't bypass C entirely
if (nxt < C) {
cur = nxt;
ans += (1 << j);
}
}
}
// 3. Right Jump Phase: Move right into the range [C, D]
for (int j = LOGN - 1; j >= 0; j--) {
int nxt = st_right[cur][j];
if (nxt != -1 && H_val[nxt] <= max_target && nxt < C) {
cur = nxt;
ans += (1 << j);
}
}
if (R[cur] != -1 && R[cur] >= C && R[cur] <= D) return ans + 1;
return -1;
}
