#include "jumps.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<int> h;
vector<int> lm;
vector<int> rm;
int n;
int arr[200100][30];
int jmp[200100][30];
int lmp[200100][30];
int rmp[200100][30];
void init(int N, std::vector<int> H) {
h=H;
n=N;
vector<pair<int,int>> stck;
lm.clear(),rm.clear();
REP(i,0,N){
while(stck.size() && stck.back().fi < H[i])stck.pop_back();
lm.pb(-1);
if(stck.size())lm.back() = (stck.back().se);
stck.pb({h[i],i});
}
stck.clear();
REP(ix,0,N){
auto i=N-1-ix;
while(stck.size() && stck.back().fi < H[i])stck.pop_back();
rm.pb(-1);
if(stck.size())rm.back() = (stck.back().se);
stck.pb({h[i],i});
}
reverse(rm.begin(),rm.end());
memset(arr,-1,sizeof arr);
memset(jmp,-1,sizeof jmp);
memset(lmp,-1,sizeof lmp);
memset(rmp,-1,sizeof rmp);
REP(i,0,N){
arr[i][0]=h[i];
lmp[i][0]=lm[i];
rmp[i][0]=rm[i];
int lc=-1,rc=-1;
if(lm[i]!=-1)lc=h[lm[i]];
if(rm[i]!=-1)rc=h[rm[i]];
if(lc > rc)jmp[i][0]=lm[i];
else if(rc > lc)jmp[i][0]=rm[i];
}
REP(j,1,30){
REP(i,0,N){
if((i+(1<<(j-1)))<N)arr[i][j]=max(arr[i][j-1],arr[i+(1<<(j-1))][j-1]);
if(jmp[i][j-1]!=-1)jmp[i][j]=jmp[jmp[i][j-1]][j-1];
if(lmp[i][j-1]!=-1)lmp[i][j]=lmp[lmp[i][j-1]][j-1];
if(rmp[i][j-1]!=-1)rmp[i][j]=rmp[rmp[i][j-1]][j-1];
}
}
}
int query(int x, int y){
int dist=y-x+1;
dist|=dist>>1;
dist|=dist>>2;
dist|=dist>>3;
dist|=dist>>4;
dist|=dist>>7;
dist|=dist>>8;
dist|=dist>>15;
dist|=dist>>16;
dist|=dist>>31;
dist++;
auto b=__builtin_ctz(dist)-1;
return max(arr[x][b],arr[y-(1<<b)+1][b]);
}
int minimum_jumps(int A, int B, int C, int D) {
// int mx=query(C,D);
int mx=0;
REP(i,C,D+1)mx=max(h[i],mx);
int b=B;
if(h[b]>mx)return -1;
REP(ix,0,25){
auto i=24-ix;
if(lmp[b][i]!=-1 && h[lmp[b][i]]<mx && lmp[b][i]>=A)b=lmp[b][i];
}
int ans=1;
// cerr<<"SELECT "<<b<<endl;
if(b==-1){return -1;}
REP(ix,0,25){
auto i=24-ix;
if(jmp[b][i]!=-1 && h[jmp[b][i]]<mx && !(C <= rm[jmp[b][i]] && rm[jmp[b][i]] <= D))b=jmp[b][i],ans+=1<<i,cerr<<b<<" "<<ans<<endl;
}
REP(ix,0,25){
auto i=24-ix;
if(lmp[b][i]!=-1 && h[lmp[b][i]]<mx && !(C <= rm[lmp[b][i]] && rm[lmp[b][i]] <= D))b=lmp[b][i],ans+=1<<i,cerr<<b<<" "<<ans<<endl;
if(rmp[b][i]!=-1 && h[rmp[b][i]]<mx && !(C <= rm[rmp[b][i]] && rm[rmp[b][i]] <= D))b=rmp[b][i],ans+=1<<i,cerr<<b<<" "<<ans<<endl;
}
if(C <= b && b <= D)return ans-1;
if(C <= rm[b] && rm[b] <= D)return ans;
if(C <= rm[lm[b]] && rm[lm[b]] <= D)return ans+1;
if(C <= rm[rm[b]] && rm[rm[b]] <= D)return ans+1;
// REP(i,A,D+1)if(h[i]>mx)return -1;
// assert(0);
return -1;
}
