#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=2e5+10;
const int MAXL=19;
int n,R[MAXN],L[MAXN],sparse[MAXN][MAXL],sp[MAXN][MAXL],jmp[MAXN][MAXL];
vector<int> v;
void init(int N, std::vector<int> H) {
v=H;
n=N;
stack<int> st;
fall(i,0,n-1) L[i]=R[i]=n;
fall(i,0,n-1){
while(sz(st)){
auto x=st.top();
if(H[x]>H[i]) break;
st.pop();
}
if(sz(st))L[i]=st.top();
st.push(i);
}
while(sz(st)) st.pop();
rfall(i,n-1,0){
while(sz(st)){
auto x=st.top();
if(H[x]>H[i]) break;
st.pop();
}
if(sz(st))R[i]=st.top();
st.push(i);
}
fall(i,0,n-1) sp[i][0]=v[i];
fall(j,1,MAXL-1)
fall(i,0,n-1){
int s=min(n-1,i+(1<<(j-1)));
sp[i][j]=max(sp[i][j-1],sp[s][j-1]);
}
fall(j,0,MAXL-1) sparse[n][j]=jmp[n][j]=n;
fall(i,0,n-1){
if(L[i]==n && R[i]==n) sparse[i][0]=n;
else if(L[i]==n || (R[i]!=n && H[R[i]]>H[L[i]])) sparse[i][0]=R[i];
else sparse[i][0]=L[i];
}
fall(j,1,MAXL-1)
fall(i,0,n-1) sparse[i][j]=sparse[sparse[i][j-1]][j-1];
fall(i,0,n-1) jmp[i][0]=R[i];
fall(j,1,MAXL-1)
fall(i,0,n-1) jmp[i][j]=jmp[jmp[i][j-1]][j-1];
}
int query(int l,int r){
int val=log2(r-l+1);
return max(sp[l][val],sp[r-(1<<val)+1][val]);
}
int minimum_jumps(int A, int B, int C, int D){
int a=A,c=C,ans=0;
if(query(A,C)!=v[c]) return -1;
rfall(i,MAXL-1,0){
int x=sparse[a][i];
if(x!=n && v[x]<=v[C]){
ans+=(1<<i);
a=x;
}
}
rfall(i,MAXL-1,0){
if(jmp[a][i]<=c){
a=jmp[a][i],ans+=(1<<i);
}
}
return ans;
}
