#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=2e5+10;
const int MAXL=19;
int n,R[MAXN],L[MAXN],sparse[MAXN][MAXL],sp[MAXN][MAXL],jmp[MAXN][MAXL];
vector<int> v;
void init(int N, std::vector<int> H) {
v=H;
n=N;
stack<int> st;
fall(i,0,n-1) L[i]=R[i]=n;
fall(i,0,n-1){
while(sz(st)){
auto x=st.top();
if(H[x]>H[i]) break;
st.pop();
}
if(sz(st))L[i]=st.top();
st.push(i);
}
while(sz(st)) st.pop();
rfall(i,n-1,0){
while(sz(st)){
auto x=st.top();
if(H[x]>H[i]) break;
st.pop();
}
if(sz(st))R[i]=st.top();
st.push(i);
}
fall(i,0,n-1) sp[i][0]=v[i];
fall(j,1,MAXL-1)
fall(i,0,n-1){
int s=min(n-1,i+(1<<(j-1)));
sp[i][j]=max(sp[i][j-1],sp[s][j-1]);
}
fall(j,0,MAXL-1) sparse[n][j]=jmp[n][j]=n;
fall(i,0,n-1){
if(L[i]==n && R[i]==n) sparse[i][0]=n;
else if(L[i]==n || (R[i]!=n && H[R[i]]>H[L[i]])) sparse[i][0]=R[i];
else sparse[i][0]=L[i];
}
fall(j,1,MAXL-1)
fall(i,0,n-1) sparse[i][j]=sparse[sparse[i][j-1]][j-1];
fall(i,0,n-1) jmp[i][0]=R[i];
fall(j,1,MAXL-1)
fall(i,0,n-1) jmp[i][j]=jmp[jmp[i][j-1]][j-1];
}
int query(int l,int r){
int val=log2(r-l+1);
return max(sp[l][val],sp[r-(1<<val)+1][val]);
}
int minimum_jumps(int A, int B, int C, int D){
int ans=0;
int ini=A,fim=B,a=-1,v1=query(C,D);
while(ini<=fim){
int mei=(ini+fim)>>1;
if(query(mei,B)>v1) ini=mei+1;
else fim=mei-1,a=mei;
}
if(a==-1) return -1;
ini=a,fim=B;
int val=query(a,B);
while(ini<=fim){
int mei=(ini+fim)>>1;
if(query(mei,B)==val) a=mei,ini=mei+1;
else fim=mei-1;
}
if(query(a,D)!=v1) return -1;
int mx=query(a,C-1),fv=0,id=0;
ini=C,fim=D;
while(ini<=fim){
int mei=(ini+fim)>>1;
if(query(C,mei)>mx) id=mei,fv=query(C,mei),fim=mei-1;
else ini=mei+1;
}
rfall(i,MAXL-1,0){
int x=sparse[a][i];
if(x!=n && v[x]<=fv){
ans+=(1<<i);
a=x;
}
}
if(v[a]==fv) return ans;
int x=sparse[a][0],cura=n+100;
if(x!=n && v[x]<=v1) cura=ans+2;
rfall(i,MAXL-1,0){
if(jmp[a][i]<=id){
a=jmp[a][i],ans+=(1<<i);
}
}
return min(ans,cura);
}
