#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll N;
vector<int> H; vector<vector<ll>> L, R, hi;
void init(int N_,vector<int> H_){
N=N_+2; H=H_; L=R=hi=vector<vector<ll>>(20,vector<ll>(N));
stack<ll> stk, stk2;
for(int i=0; i<N; i++){
while(!stk.empty() && H[stk.top()]<=H[i]) stk.pop();
if(stk.empty()) L[0][i]=i;
else L[0][i]=stk.top();
stk.push(i);
}
for(int i=N-1; i>=0; i--){
while(!stk2.empty() && H[stk2.top()]<=H[i]) stk2.pop();
if(stk2.empty()) R[0][i]=i;
else R[0][i]=stk2.top();
stk2.push(i);
}
for(int i=0; i<N; i++){
if(H[L[0][i]]>H[R[0][i]]) hi[0][i]=L[0][i];
else hi[0][i]=R[0][i];
}
for(int i=1; i<20; i++){
for(int j=0; j<N; j++){
L[i][j]=L[i-1][L[i-1][j]];
R[i][j]=R[i-1][R[i-1][j]];
hi[i][j]=hi[i-1][hi[i-1][j]];
}
}
}
int minimum_jumps(int A,int B,int C,int D) {
ll ans=0;
auto query=[&](ll l,ll r){
for(int i=19; i>=0; i--){
if(R[i][l]<=r) l=R[i][l];
}
return l;
};
if(B==C-1){
if(R[0][B]<=D) return 1;
else return -1;
}
ll x=query(B+1,C-1);
if(H[B]>H[x]){
if(R[0][B]<=D) return 1;
else return -1;
}
for(int i=19;i>=0; i--){
if(A<=L[i][B] && H[L[i][B]]<H[x]) B=L[i][B];
}
if(A<=L[0][B]){
if(R[0][L[0][B]]<=D) return 1;
for(int i=19; i>=0; i--){
if(H[hi[i][B]]<=H[x]){
ans|=(1<<i);
B=hi[i][B];
}
}
if(B==x){
if(R[0][B]<=D) return ans+1;
else return -1;
}
if(0<L[0][B] && R[0][L[0][B]]<=D) return ans+2;
}
for(int i=19; i>=0; i--){
if(R[i][B]<C){
ans+=(1<<i);
B=R[i][B];
}
}
if(C<=R[0][B] && R[0][B]<=D) return ans+1;
else return -1;
}
