#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;
struct segtree {
int n;
vector<int> t;
segtree(int n) {
this -> n = n;
t.assign(4 * n + 4, inf);
}
void upd(int v, int tl, int tr, int i, int delta) {
if (tl == tr) {
t[v] = delta;
return;
}
int tm = (tl + tr) / 2;
if (tm >= i) upd(2 * v, tl, tm, i, delta);
else upd(2 * v + 1, tm + 1, tr, i, delta);
t[v] = min(t[2 * v], t[2 * v + 1]);
} void upd(int i, int delta) {
upd(1, 1, n, i, delta);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return inf;
if (tl >= l && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return min(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
} int get(int l, int r) {
return get(1, 1, n, l, r);
}
};
int n;
vector<int> h, l, r;
vector<vector<int>> d;
vector<segtree> T;
void init(int N, std::vector<int> H) {
n = N, h = H;
l.resize(n), r.resize(n), d.resize(n);
iota(all(l), 0ll), iota(all(r), 0ll);
for (int i = 0; i < n; ++i) {
d[i].assign(n, inf);
}
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (h[i] < h[j]) {
l[i] = j;
break;
}
}
for (int j = i + 1; j < n; ++j) {
if (h[i] < h[j]) {
r[i] = j;
break;
}
}
}
vector<segtree> t(n, segtree(n));
for (int i = 0; i < n; ++i) {
d[i][i] = 0;
queue<int> q;
q.push(i);
while (!q.empty()) {
int v = q.front();
q.pop();
if (chmin(d[i][l[v]], d[i][v] + 1)) {
q.push(l[v]);
}
if (chmin(d[i][r[v]], d[i][v] + 1)) {
q.push(r[v]);
}
}
for (int j = 0; j < n; ++j) {
t[i].upd(j + 1, d[i][j]);
}
}
T = t;
}
int minimum_jumps(int A, int B, int C, int D) {
if (n <= 2000) {
int res = inf;
for (int i = A; i <= B; ++i) {
chmin(res, T[i].get(C + 1, D + 1));
}
return res == inf ? -1 : res;
} else {
return C - B;
}
}
