#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;\
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
const ll INF=1000000000000000010;
const int inf=1e9+10;
const ll M=1e9+7;
int n,k;
vii x,y,z;
void init(int N, std::vector<int> H) {
n=N;
k=log2(n)+1;
x.resize(n,vi(k,-1)),y.resize(n,vi(k,inf)),z.resize(n,vi(k,inf));
stack<pi> st;
st.push({H[0],0});
REP(i,1,n){
if(st.top().F<H[i]){
while(!st.empty()&&st.top().F<H[i]){
x[st.top().S][0]=i;
z[st.top().S][0]=i;
st.pop();
}
}
st.push({H[i],i});
}
st=stack<pi>();
st.push({H[n-1],n-1});
for(int i=n-2;i>=0;i--){
if(st.top().F<H[i]){
while(!st.empty()&&st.top().F<H[i]){
y[st.top().S][1]=i;
st.pop();
}
}
st.push({H[i],i});
}
REP(i,0,n){
if(x[i][0]==-1)x[i][0]=inf;
if(y[i][0]==inf)y[i][0]=-1;
}
REP(j,1,k)REP(i,0,n)if(z[i][j-1]!=inf)z[i][j]=z[z[i][j-1]][j-1];
REP(j,1,k){
REP(i,0,n){
if(x[i][j-1]!=inf)x[i][j]=max(x[i][j],x[x[i][j-1]][j-1]);
if(y[i][j-1]!=-1)x[i][j]=max(x[i][j],x[y[i][j-1]][j-1]);
if(x[i][j-1]!=inf)y[i][j]=min(y[i][j],y[x[i][j-1]][j-1]);
if(y[i][j-1]!=-1)y[i][j]=min(y[i][j],y[y[i][j-1]][j-1]);
}
REP(i,0,n){
if(x[i][j]==-1)x[i][j]=inf;
if(y[i][j]==inf)y[i][j]=-1;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ans=0,l=A,r=B;
for(int j=k-1;j>=0;j--){
if(l!=-1&&x[A][j]>C&&x[B][j]>C)continue;
if(l==-1&&x[B][j]>C)continue;
ans+=(1<<j);
if(l!=-1)A=min(y[l][j],y[r][j]);
if(l!=-1){
if(x[l][j]==inf)B=x[r][j];
else if(x[r][j]==inf)B=x[l][j];
else B=max(x[l][j],x[r][j]);
}
else B=x[r][j];
l=A;r=B;
}
if(r==C)return ans;
for(int j=k-1;j>=0;j--){
if(z[r][j]>C)continue;
ans+=(1<<j);
r=z[r][j];
}
if(r==C)return ans;
return -1;
}
