#include<bits/stdc++.h>
#include"jumps.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 200005
int t[4*N],arr[N],up[20][N],dow[20][N],n;
void cre(int x,int l,int r){
if(l==r){t[x]=arr[l];return ;}
int mid=(l+r)/2;
cre(x*2,l,mid);
cre(x*2+1,mid+1,r);
t[x]=max(t[x*2],t[x*2+1]);
}
int sol(int x,int l,int r,int ll,int rr){
if(l>rr||ll>r||ll>rr)return 0;
if(ll<=l&&r<=rr)return t[x];
int mid=(l+r)/2;
return max(sol(x*2,l,mid,ll,rr),sol(x*2+1,mid+1,r,ll,rr));
}
void init(int nn,vector<int> h){
int i,j,l,r,mid,val;
n=nn;
for(i=0;i<n;i++)arr[i+1]=h[i];
cre(1,1,n);
arr[n+1]=n+1;
for(i=0;i<20;i++)for(j=0;j<=n+1;j++)up[i][j]=dow[i][j]=n+1;
for(i=1;i<=n;i++){
l=1,r=i-1;
while(l<=r){
mid=(l+r)/2;
if(sol(1,1,n,mid,i-1)>arr[i])dow[0][arr[i]]=arr[mid],l=mid+1;
else r=mid-1;
}
l=i+1,r=n;
while(l<=r){
mid=(l+r)/2;
if(sol(1,1,n,i+1,mid)>arr[i])up[0][arr[i]]=arr[mid],r=mid-1;
else l=mid+1;
}
if(up[0][arr[i]]<dow[0][arr[i]])swap(up[0][arr[i]],dow[0][arr[i]]);
}
for(i=1;i<20;i++)for(j=1;j<=n;j++){
up[i][j]=up[i-1][up[i-1][j]];
dow[i][j]=dow[i-1][dow[i-1][j]];
}
return ;
}
int minimum_jumps(int a,int b,int c,int d){
a++,b++,c++,d++;
int i,l,r,mid,ml,mm,mr,now,val,ans=0;
mm=sol(1,1,n,c+1,d-1);
mr=sol(1,1,n,c,d);
if(mm>mr)return -1;
l=c,r=d;
while(l<=r){
mid=(l+r)/2;
if(sol(1,1,n,c,mid)>mm)ml=arr[mid],r=mid-1;
else l=mid+1;
}
l=a,r=b;
now=n+1;
while(l<=r){
mid=(l+r)/2;
val=sol(1,1,n,mid,b);
if(val<mr)now=val,r=mid-1;
else l=mid+1;
}
if(now>mr)return -1;
for(i=19;i>=0;i--)if(up[i][now]<ml)ans+=1<<i,now=up[i][now];
if(up[0][now]>=ml&&up[0][now]<=mr)return ans+1;
for(i=19;i>=0;i--)if(dow[i][now]<ml)ans+=1<<i,now=dow[i][now];
if(dow[0][now]>=ml&&dow[0][now]<=mr)return ans+1;
return -1;
}
