#include "jumps.h"
int pie(int army){return (1<<army);}
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int lef[200000][18],rig[200000][18],smart[200000][18][2];
int cal(int pos,int C,int D){
int ans=0;
int mn=pos,mx=pos;
for(int i=18-1;i>=0;i--){
if(max(smart[mx][i][1],smart[mn][i][1])>=C)continue;
ans+=pie(i);
int tmp;
tmp=min(smart[mx][i][0],smart[mn][i][0]);
mx=max(smart[mx][i][1],smart[mn][i][1]);
mn=tmp;
}
if((smart[mx][0][1]>=C&&smart[mx][0][1]<=D)||(smart[mn][0][1]>=C&&smart[mn][0][1]<=D))return ans+1;
for(int i=18-1;i>=0;i--){
if(rig[mx][i]>=C)continue;
ans+=pie(i);
mx=rig[mx][i];
}
mx=rig[mx][0];
if(mx>=C&&mx<=D)return ans+1;
return -1;
}
int minimum_jumps(int A,int B,int C,int D){
int ans=cal(B,C,D);
if(ans==-1)return ans;
int pos=B;
for(int i=18-1;i>=0;i--){
if(lef[pos][i]<A)continue;
int res=cal(lef[pos][i],C,D);
if(res==-1)continue;
pos=lef[pos][i];
ans=res;
}
return ans;
}
void init(int N,vector<int> H){
vector<int>sta;
for(int i=0;i<N;i++){
while(sta.size()&&H[sta.back()]<H[i])sta.pop_back();
if(sta.size()==0)lef[i][0]=i;
else lef[i][0]=sta.back();
sta.pb(i);
}
sta.clear();
for(int i=N-1;i>=0;i--){
while(sta.size()&&H[sta.back()]<H[i])sta.pop_back();
if(sta.size()==0)rig[i][0]=i;
else rig[i][0]=sta.back();
sta.pb(i);
}
for(int i=0;i<N;i++){
smart[i][0][0]=lef[i][0];
smart[i][0][1]=rig[i][0];
}
for(int i=1;i<18;i++){
for(int j=0;j<N;j++){
lef[j][i]=lef[lef[j][i-1]][i-1];
rig[j][i]=rig[rig[j][i-1]][i-1];
smart[j][i][0]=min(smart[smart[j][i-1][0]][i-1][0],smart[smart[j][i-1][1]][i-1][0]);
smart[j][i][1]=max(smart[smart[j][i-1][0]][i-1][1],smart[smart[j][i-1][1]][i-1][1]);
}
}
}
