#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;
const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector<int> l(N), r(N);
int n;
void init(int N, vector<int> H) {
n = N;
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() and H[s.top()] < H[i]) s.pop();
r[i] = s.empty() ? n : s.top();
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = 0; i < n; i++) {
while (!s.empty() and H[s.top()] < H[i]) s.pop();
l[i] = s.empty() ? -1 : s.top();
s.push(i);
}
}
int minimum_jumps(int a, int b, int c, int d) {
queue<int> q;
vector<int> ans(n, inf);
for (int i = a; i <= b; i++) ans[i] = 0, q.push(i);
while (!q.empty()) {
int x = q.front(); q.pop();
if (c <= x and x <= d) return ans[x];
if (l[x] >= 0 and ans[l[x]] > ans[x] + 1) {
ans[l[x]] = ans[x] + 1;
q.push(l[x]);
}
if (r[x] < n and ans[r[x]] > ans[x] + 1) {
ans[r[x]] = ans[x] + 1;
q.push(r[x]);
}
}
return -1;
}
