#include "jumps.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long
using namespace std;
vector <array<ll, 2> > V;
array<ll, 2> L[200000], R[200000];
ll n, z, s, k, X[200000], jmp[200000][18], bl[200000][18], st[800000];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = X[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = max(st[id*2], st[id*2+1]);
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return -1;
else if (ql <= l && r <= qr) return st[id];
ll mid = (l+r)/2;
return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
}
void find(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return;
if (l == r) {
s = l;
return;
}
ll mid = (l+r)/2;
if (ql <= l && r <= qr) {
if (st[id*2] < st[id*2+1]) find(id*2+1, mid+1, r, ql, qr);
else find(id*2, l, mid, ql, qr);
return;
}
find(id*2, l, mid, ql, qr);
find(id*2+1, mid+1, r, ql, qr);
}
void solve(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql || k == -1) return;
ll mid = (l+r)/2;
if (ql <= l && r <= qr) {
if (st[id] >= z) {
if (l == r) {
k = l;
return;
}
solve(id*2+1, mid+1, r, ql, qr);
solve(id*2, l, mid, ql, qr);
}
return;
}
solve(id*2+1, mid+1, r, ql, qr);
solve(id*2, l, mid, ql, qr);
}
void init(int N, std::vector<int> H) {
n = N;
for (int i=0; i<N; ++i) {
X[i] = H[i];
}
build(1, 0, n-1);
ll l, r, mid;
for (int i=0; i<n; ++i) {
L[i] = {-1, -1};
l = 0, r = (ll)V.size()-1;
while (l < r) {
mid = (l+r+1)/2;
if (V[mid][0] > X[i]) l = mid;
else r = mid-1;
}
if (!V.empty() && V[l][0] > X[i]) {
L[i] = {V[l][1], V[l][0]};
}
while (!V.empty()) {
auto [u, x] = V.back();
if (X[i] > u) V.pop_back();
else break;
}
V.push_back({X[i], i});
}
V.clear();
for (int i=n-1; i>=0; --i) {
R[i] = {-1, -1};
bl[i][0] = i;
l = 0, r = (ll)V.size()-1;
while (l < r) {
mid = (l+r+1)/2;
if (V[mid][0] > X[i]) l = mid;
else r = mid-1;
}
if (!V.empty() && V[l][0] > X[i]) {
bl[i][0] = V[l][1];
R[i] = {V[l][1], V[l][0]};
}
while (!V.empty()) {
auto [u, x] = V.back();
if (X[i] > u) V.pop_back();
else break;
}
V.push_back({X[i], i});
}
for (int i=0; i<n; ++i) {
if (L[i][1] && R[i][1] == -1) jmp[i][0] = i;
else if (L[i][1] > R[i][1]) jmp[i][0] = L[i][0];
else jmp[i][0] = R[i][0];
}
for (int j=1; j<18; ++j) {
for (int i=0; i<n; ++i) {
bl[i][j] = bl[bl[i][j-1]][j-1];
jmp[i][j] = jmp[jmp[i][j-1]][j-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
z = query(1, 0, n-1, C, D);
k = -1;
solve(1, 0, n-1, A, B);
if (k == B) return -1;
if (k == -1) k = A;
else ++k;
find(1, 0, n-1, k, B);
ll f = 0;
for (int j=17; j>=0; --j) {
if (X[jmp[s][j]] < z) {
if (bl[jmp[s][j]][0] < C) {
s = jmp[s][j];
f += (1LL<<j);
}
}
}
for (int j=17; j>=0; --j) {
if (bl[s][j] < C) {
s = bl[s][j];
f += (1LL<<j);
}
}
if (C <= bl[s][0] && bl[s][0] <= D) return f+1;
else return -1;
}
