#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2e5+50,inf=1e9,lg=18;
int n,a[N],ind[N],Lv[N],Rv[N],par[N][lg+1],par2[N][lg+1];
int Maks[N][lg+1],LOG[N+50];
int Get(int l,int r){if(l>r)return 0;int i=LOG[r-l+1];return max(Maks[l][i],Maks[r-(1<<i)+1][i]);}
void init(int n1,vector<int>H){
n=n1;for(int i=1;i<=n;i++) a[i]=H[i-1];
vector<int>mono;
for(int i=1;i<=n;i++){
while(!mono.empty()&&a[mono.back()]<a[i]){
Rv[mono.back()]=i;
mono.pop_back();
}
if(!mono.empty()) Lv[i]=mono.back();
mono.pb(i);
}
a[0]=inf;
for(int i=1;i<=n;i++){
if(Lv[i]==0) par[i][0]=Rv[i];
else if(Rv[i]==0) par[i][0]=Lv[i];
else if(a[Lv[i]]>a[Rv[i]]) par[i][0]=Lv[i];
else par[i][0]=Rv[i];
par2[i][0]=Rv[i];
}
for(int j=1;j<=lg;j++){
for(int i=1;i<=n;i++){
par[i][j]=par[par[i][j-1]][j-1];
par2[i][j]=par2[par2[i][j-1]][j-1];
}
}
for(int i=1;i<=n;i++) ind[a[i]]=i;
for(int i=1;i<=n;i++) Maks[i][0]=a[i];
for(int i=1,e=1,ct=-1;i<=N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
for(int j=0;j<lg;j++){
for(int i=1;i<=n;i++){
if(i+(1<<j)<=n) Maks[i][j+1]=max(Maks[i][j],Maks[i+(1<<j)][j]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++,B++,C++,D++;
int X=Get(B,C-1),Y=Get(C,D);
if(X>Y) return -1;
int l=A,r=B,val=0;
while(l<=r){
int mid=l+r>>1;
int x=Get(mid,B);
if(Get(mid,B)<Y){r=mid-1;val=x;}
else l=mid+1;
}
int u=ind[val],res=0;
for(int i=lg;i>=0;i--){
if(par[u][i]&&a[par[u][i]]<X){
u=par[u][i];
res+=1<<i;
}
}
if(Rv[u]>=C) return res+1;
if(par[u][0]&&a[par[u][0]]<Y) return res+2;
for(int i=lg;i>=0;i--){
if(par2[u][i]&&par2[u][i]<C){
u=par2[u][i];
res+=1<<i;
}
}
return res+1;
}
