#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,lg=20;
int inf=1e9,kaf=(1<<19);
int n,all[maxn],fr[maxn],fl[maxn],sp[lg][maxn],spr[lg][maxn],mxsp[lg][maxn];
struct segmentmx{
int seg[(1<<20)];
void ins(int i,int w){
i+=kaf;
while(i>0){
seg[i]=max(w,seg[i]);
i>>=1;
}
}
int pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}segmax;
void pre(){
all[0]=all[n+1]=inf;
vector<int>v;
v.push_back(0);
for(int i=1;i<=n;i++){
segmax.ins(i,all[i]);
while((int)v.size()>0&&all[v.back()]<=all[i]){
v.pop_back();
}
fl[i]=v.back();
v.push_back(i);
}
v.clear();
v.push_back(n+1);
for(int i=n;i>=1;i--){
while((int)v.size()>0&&all[v.back()]<=all[i]){
v.pop_back();
}
fr[i]=v.back();
v.push_back(i);
mxsp[0][i]=fr[i];
}
mxsp[0][n+1]=n+1;
for(int i=1;i<=n;i++){
spr[0][i]=fr[i];
if(all[fr[i]]>=all[fl[i]]){
sp[0][i]=fr[i];
}else{
sp[0][i]=fl[i];
}
}
for(int i=1;i<lg;i++){
for(int j=1;j<=n;j++){
sp[i][j]=sp[i-1][sp[i-1][j]];
spr[i][j]=spr[i-1][spr[i-1][j]];
mxsp[i][j]=max(mxsp[i-1][j],mxsp[i-1][sp[i-1][j]]);
}
}
}
void init(int N,vector<int> H) {
n=N;
for(int i=1;i<=n;i++){
all[i]=H[i-1];
}
pre();
}
int cal(int a,int b,int c,int mx){
if(all[a]>=mx){
return inf;
}
int ret=0;
for(int i=lg-1;i>=0;i--){
if(sp[i][a]!=0&&all[sp[i][a]]<mx&&mxsp[i][a]<b){
ret+=(1<<i);
a=sp[i][a];
if(a>=b&&a<=c){
return ret;
}
}
}
for(int i=lg-1;i>=0;i--){
if(spr[i][a]!=0&&spr[i][a]<b){
a=spr[i][a];
ret+=(1<<i);
}
}
if(all[a]>=mx){
return inf;
}
return ret+1;
}
int solve(int a,int b,int c,int d){
int mxb=segmax.pors(1,0,kaf-1,c,d);
int low=a-1,high=b,mid;
while(high-low>1){
mid=(high+low)>>1;
if(segmax.pors(1,0,kaf-1,mid,b)<mxb){
high=mid;
}else{
low=mid;
}
}
int z=segmax.pors(1,0,kaf-1,high,b);
low=a,high=b+1;
while(high-low>1){
mid=(high+low)>>1;
if(segmax.pors(1,0,kaf-1,mid,b)>=z){
low=mid;
}else{
high=mid;
}
}
/*int wh=b,mx=all[b];
for(int i=b-1;i>=a;i--){
if(all[i]>=mxb){
break;
}
if(all[i]>mx){
mx=all[i];
wh=i;
}
}*/
int res=cal(low,c,d,mxb);
if(res>=inf){
res=-1;
}
return res;
}
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
return solve(A,B,C,D);
}
