#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int i, n, x;
stack<pair<int, int> > S;
queue<int> Q;
vector<int> adj[200005];
int d[200005];
const int INF = INT_MAX;
void init(int N, vector<int> H) {
n = N;
for (i=0; i < N; ++i) {
while (!S.empty() && S.top().X < H[i]) S.pop();
if (!S.empty()) adj[i].push_back(S.top().Y);
S.push(make_pair(H[i], i));
}
while (!S.empty()) S.pop();
for (i=N-1; i >= 0; --i) {
while (!S.empty() && S.top().X < H[i]) S.pop();
if (!S.empty()) adj[i].push_back(S.top().Y);
S.push(make_pair(H[i], i));
}
}
int minimum_jumps(int A, int B, int C, int D) {
fill(d, d+n, INF);
while (!Q.empty()) Q.pop();
for (i=A; i <= B; ++i) {
Q.push(i);
d[i] = 0;
}
while (!Q.empty()) {
x = Q.front();
Q.pop();
for (auto y : adj[x]) {
if (C <= y && y <= D) return d[x]+1;
if (d[y] == INF) {
Q.push(y);
d[y] = d[x]+1;
}
}
}
return -1;
}
