#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int M=2e5+10;
int dl[M][20],dh[M][20],g[M][20],gmx[M][20],jr[M][20];
vector<int> tH;
int nl[M],nr[M],n;
int fmx(int l,int r){
if(l>r) return INT_MIN;
int now=l;
int mx=INT_MIN;
for(int i=19;i>=0;i--){
if(now+(1<<i)<=r+1) mx=max(mx,gmx[now][i]),now+=(1<<i),now=min(now,n-1);
}
return mx;
}
void init(int N, std::vector<int> H) {
stack<int> st;
n=N;
for(int i=0;i<N;i++) nl[i]=nr[i]=N;
for(int i=0;i<N;i++){
while(!st.empty() && H[st.top()]<H[i]) st.pop();
if(!st.empty()) nl[i]=st.top(),g[i][0]=st.top();
else g[i][0]=N;
st.push(i);
gmx[i][0]=H[i];
}
while(!st.empty()) st.pop();
for(int i=N-1;i>=0;i--){
while(!st.empty() && H[st.top()]<H[i]) st.pop();
if(!st.empty()) nr[i]=st.top(),jr[i][0]=st.top();
else jr[i][0]=N;
st.push(i);
}
dl[N][0]=dh[N][0]=g[N][0]=jr[N][0]=N;
H.push_back(INT_MAX);
tH=H;
for(int i=0;i<N;i++){
if(H[nl[i]]<H[nr[i]]) dl[i][0]=nl[i],dh[i][0]=nr[i];
else dl[i][0]=nr[i],dh[i][0]=nl[i];
}
for(int i=1;i<20;i++) for(int j=0;j<=N;j++){
dl[j][i]=dl[dl[j][i-1]][i-1];
dh[j][i]=dh[dh[j][i-1]][i-1];
g[j][i]=g[g[j][i-1]][i-1];
gmx[j][i]=max(gmx[j][i-1],gmx[min(N-1,j+(1<<(i-1)))][i-1]);
jr[j][i]=jr[jr[j][i-1]][i-1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
int now=B;
int bd=fmx(C,D);
for(int i=19;i>=0;i--){
int cd=g[now][i];
if(cd<A) continue;
if(cd==n) continue;
if(tH[cd]<bd && fmx(cd+1,C-1)<bd) now=cd;
}
int cp=now;
if(tH[now]>bd || fmx(now+1,C-1)>bd) return -1;
int ret=0;
//cout<<"START" <<now <<"\n";
for(int i=19;i>=0;i--){
int cd=dh[now][i];
if(cd==n) continue;
if(cd>D) continue;
if(C<=jr[cd][0] && jr[cd][0]<=D) continue;
if(cd<C && tH[cd]<=bd && fmx(cd+1,D)<=bd){
now=cd,ret+=(1<<i);
}
}
if(C<=dh[now][0] && dh[now][0]<=D) return ret+1;
//<<now <<" " <<ret <<"\n";
for(int i=19;i>=0;i--){
int cd=jr[now][i];
if(cd==n) continue;
if(jr[now][i]<C) now=cd,ret+=(1<<i);
}
if(C<=now && now<=D) return ret;
ret++;
return ret;
}
