#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
template<class S, class T>
bool chmin(S& a, const T& b) {
return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
return a < b ? (a = b) == b : false;
}
const int inf = 1e9;
int n;
vector<int> h, l, r;
bool increasing = true;
void init(int N, std::vector<int> H) {
n = N, h = H;
for (int i = 1; i < n; ++i) {
if (h[i] <= h[i - 1]) increasing = false;
}
l.resize(n), r.resize(n);
iota(all(l), 0ll), iota(all(r), 0ll);
stack<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && h[stk.top()] >= h[i]) {
stk.pop();
}
if (!stk.empty()) l[i] = stk.top();
stk.push(i);
}
while (!stk.empty()) stk.pop();
for (int i = n - 1; i >= 0; --i) {
while (!stk.empty() && h[stk.top()] >= h[i]) {
stk.pop();
}
if (!stk.empty()) r[i] = stk.top();
stk.push(i);
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (increasing) {
return C - B;
} else {
vector<int> d(n, inf);
queue<int> q;
for (int i = C; i <= D; ++i) {
q.push(i);
d[i] = 0;
}
while (!q.empty()) {
int v = q.front();
q.pop();
if (chmin(d[l[v]], d[v] + 1)) {
q.push(l[v]);
}
if (chmin(d[r[v]], d[v] + 1)) {
q.push(r[v]);
}
}
int res = inf;
for (int i = A; i <= B; ++i) {
chmin(res, d[i]);
}
return res == inf ? -1 : res;
}
}
