#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
const int INF = 1e9;
struct node {
int left = -1;
int right = -1;
};
vector<node> nodes;
void init(int N, vector<int> H) {
n = N;
h = H;
nodes = vector<node>(n);
for (int i = 1; i < n; i++) {
int target = i - 1;
while (H[target] <= H[i]) {
if (target == -1) {
break;
}
target = nodes[target].left;
}
nodes[i].left = target;
}
for (int i = n - 2; i >= 0; i--) {
int target = i + 1;
while (H[target] <= H[i]) {
if (target == -1) {
break;
}
target = nodes[target].right;
}
nodes[i].right = target;
}
// for (int i = 0; i < n; i++) {
// int left = -1;
// int right = -1;
// for (int j = i - 1; j >= 0; j--) {
// if (H[j] > H[i]) {
// left = j;
// break;
// }
// }
// for (int j = i + 1; j < n; j++) {
// if (H[j] > H[i]) {
// right = j;
// break;
// }
// }
// nodes[i].left = left;
// nodes[i].right = right;
// }
return;
}
int next_jump(int a, int c) {
if (a == -1) {
return -1;
}
int greatest = -1;
int ancestor = -1;
if (nodes[a].left != -1 && greatest < h[nodes[a].left] && h[nodes[a].left] <= h[c]) {
greatest = h[nodes[a].left];
ancestor = nodes[a].left;
}
if (nodes[a].right != -1 && greatest < h[nodes[a].right] && h[nodes[a].right] <= h[c]) {
greatest = h[nodes[a].right];
ancestor = nodes[a].right;
}
return ancestor;
}
int minimum_jumps(int A, int B, int C, int D) {
// Start the BFS
vector<int> dist(n + 10, INF);
queue<int> q;
for (int i = A; i <= B; i++) {
dist[i] = 0;
q.push(i);
}
while (!q.empty()) {
int source = q.front(); q.pop();
if (next_jump(source, C) != -1) {
q.push(next_jump(source, C));
dist[next_jump(source, C)] = 1 + dist[source];
}
}
int smallest = INF;
for (int i = C; i <= D; i++) {
smallest = min(smallest, dist[i]);
}
if (smallest == INF) {
return -1;
}
return smallest;
}
