#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int B = 20;
int n;
vector<vector<int>> build(vector<vector<int>> g,vector<int>rt){
vector<vector<int>> up(n+1);
function<void(int,int )> dfs = [&](int v,int pr) {
up[v].resize(B);
up[v][0] = pr;
for(int i = 1;i < B;i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to:g[v]) {
dfs(to,v);
}
};
for(int i:rt) {
dfs(i,i);
}
return up;
}
const int maxn = (int)1e5 + 12;
int L[maxn],R[maxn];
vector<int> h;
void init(int N, vector<int> H) {
h = H;
n = N;
n = N;
vector<int> st,rt;
vector<vector<int>> G(n);
for(int i = 0;i < N;i++) {
while(!(int)st.empty() && H[st.back()] < H[i]) {
st.pop_back();
}
if(st.empty()) {
L[i] = -1;
}else {
L[i] = st.back();
}
st.push_back(i);
}
st.clear();
for(int i = N - 1;i >= 0;i--){
while(!st.empty() && H[st.back()] < H[i]){
st.pop_back();
}
if(st.empty()) {
R[i] = -1;
}else {
R[i] = st.back();
}
st.push_back(i);
}
}
int go(int v,int C,int D,int mx){
// cerr << v << ' ' << R[v] << ' ' << L[v] << 'n'
if(v >= C && v <= D){
return 0;
}
if(L[v] == -1 || (R[v] != -1 && (h[L[v]] > mx || h[L[v]] < h[R[v]]))) {
if(R[v] == -1) return (int)1e9;
return go(R[v],C,D,mx) + 1;
}
return go(L[v],C,D,mx) + 1;
}
int minimum_jumps(int A, int B, int C, int D) {
int mx = 0;
for(int i = C;i <= D;i++){
mx = max(mx,h[i]);
}
int res = (int)1e9;
for(int i = A;i <= B;i++){
res = min(res,go(i,C,D,mx));
}
if(res == (int)1e9) res = -1;
return res;
}
