#include <bits/stdc++.h>
using namespace std;
int n;
const int INF = 1e9;
struct node {
int left = -1;
int right = -1;
};
vector<node> nodes;
void init(int N, vector<int> H) {
n = N;
nodes = vector<node>(n);
// Precomputing the left value.
set<int> heights_l;
vector<int> last_val_l(n + 1, -1);
for (int i = 0; i < n; i++) {
auto it = heights_l.upper_bound(H[i]);
if (it != heights_l.end()) {
nodes[i].left = last_val_l[*it];
}
heights_l.insert(H[i]);
last_val_l[H[i]] = i;
}
// Precomputing the right values.
set<int> heights_r;
vector<int> last_val_r(n + 1, -1);
for (int i = n - 1; i >= 0; i--) {
auto it = heights_r.upper_bound(H[i]);
if (it != heights_r.end()) {
nodes[i].right = last_val_r[*it];
}
heights_r.insert(H[i]);
last_val_r[H[i]] = i;
}
// for (int i = 0; i < n; i++) {
// cout << "Node " << i << ": " << nodes[i].left << ' ' << nodes[i].right << '\n';
// }
return;
}
int minimum_jumps(int A, int B, int C, int D) {
// Start the BFS
vector<int> dist(n + 10, INF);
queue<int> q;
// cout << A << ' ' << B << ' ' << nodes.size() << '\n';
for (int i = A; i <= B; i++) {
dist[i] = 0;
q.push(i);
}
while (!q.empty()) {
int source = q.front(); q.pop();
// cout << "Source: " << source << '\n';
if (dist[nodes[source].left] == INF) {
q.push(nodes[source].left);
dist[nodes[source].left] = 1 + dist[source];
}
if (dist[nodes[source].right] == INF) {
q.push(nodes[source].right);
dist[nodes[source].right] = 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;
}
