#include "jumps.h"
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
int n;
int lef[200002][18],rig[200002][18],smart[200002][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){
A++;B++;C++;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){
n=N;
int arr[n+2];
for(int i=1;i<=n;i++){
arr[i]=H[i-1];
}
vector<int>sta;
for(int i=1;i<=n;i++){
while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back();
if(sta.size()==0)lef[i][0]=i;
else lef[i][0]=sta.back();
sta.pb(i);
}
while(sta.size())sta.pop_back();
for(int i=n;i>=1;i--){
while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back();
if(sta.size()==0)rig[i][0]=i;
else rig[i][0]=sta.back();
sta.pb(i);
}
for(int i=1;i<18;i++){
for(int j=1;j<=n;j++){
lef[j][i]=lef[lef[j][i-1]][i-1];
rig[j][i]=rig[rig[j][i-1]][i-1];
}
}
for(int i=1;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=1;j<=n;j++){
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]);
}
}
}
