#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;
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), d.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);
}
if (n <= 2000) {
for (int i = 0; i < n; ++i) {
d[i].assign(n, inf);
}
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 = C; i <= D; ++i) {
chmin(res, T[i].get(A + 1, B + 1));
}
return res == inf ? -1 : res;
} else 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;
}
}
