// Code by Parsa Eslami
#include <bits/stdc++.h>
#include "jumps.h"
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
using namespace std;
const int N=2e5+4;
const int lg=20;
int pw[lg],SM[lg][N],RR[N],LL[N],opt[lg][N],R[lg][N];
int MX(int l,int r){
if(l>r) return 0;
int LG=31-__builtin_clz(r-l+1);
return max(SM[LG][l],SM[LG][r-pw[LG]+1]);
}
void init(int n,vector<int> H){
pw[0]=1; FOR(j,1,lg-1) pw[j]=pw[j-1]*2;
int h[n+1];
FOR(i,1,n) h[i]=H[i-1];
FOR(i,1,n) SM[0][i]=h[i];
FOR(j,1,lg-1) FOR(i,1,n-pw[j]+1) SM[j][i]=max(SM[j-1][i],SM[j-1][i+pw[j-1]]);
vector<int> vc;
FOR(i,1,n){
while(!vc.empty()&&vc.back()<h[i]){
RR[vc.back()]=h[i];
vc.pop_back();
}
vc.pb(h[i]);
}
vc.clear();
FORR(i,n,1){
while(!vc.empty()&&vc.back()<h[i]){
LL[vc.back()]=h[i];
vc.pop_back();
}
vc.pb(h[i]);
}
FOR(i,1,n) opt[0][i]=max(LL[i],RR[i]);
FOR(j,1,lg-1) FOR(i,1,n) opt[j][i]=opt[j-1][opt[j-1][i]];
FOR(i,1,n) R[0][i]=RR[i];
FOR(j,1,lg-1) FOR(i,1,n) R[j][i]=R[j-1][R[j-1][i]];
}
int minimum_jumps(int A,int B,int C,int D){
A++; B++; C++; D++;
int bmx=MX(C,D);
int mx=MX(B+1,C-1);
int l=A-1,r=B+1;
while(r-l>1){
int mid=(r+l)/2;
if(MX(mid,B)<=bmx) r=mid;
else l=mid;
}
if(r==B+1) return -1;
if(mx>bmx) return -1;
int amx=MX(r,B);
if(amx>mx) return 1;
int rt=0;
int v=amx;
FORR(j,lg-1,0) if(opt[j][v]&&opt[j][v]<mx){
v=opt[j][v];
rt+=pw[j];
}
if((LL[v]>mx&&LL[v]<bmx)||(RR[v]==mx)) return (rt+2);
FORR(j,lg-1,0) if(R[j][v]&&R[j][v]<mx){
v=R[j][v];
rt+=pw[j];
}
return (rt+2);
}
