#include "jumps.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 2e5 + 5;
const int lg = 18;
int n; vi h; int a[mxn][lg], b[mxn][lg], L[mxn], R[mxn];
struct segtree{
int n; vi mx, mn;
segtree(){}
segtree(int x){
n=x; mx.resize(2*n+5); mn.resize(2*n+5);
}
void update(int k, int x){
k+=n;mn[k]=mx[k]=x; for(k/=2;k>=1;k/=2)mn[k]=min(mn[k*2],mn[k*2+1]),mx[k]=max(mx[k*2],mx[k*2+1]);
}
int quermin(int l, int r){
int ret = 4e18; l+=n;r+=n; while(l<=r){
if(l%2)ret=min(ret,mn[l++]); if(r%2==0)ret=min(ret,mn[r--]); l/=2; r/=2;
} return ret;
}
int quermax(int l, int r){
int ret = -4e18; l+=n;r+=n; while(l<=r){
if(l%2)ret=max(ret,mx[l++]); if(r%2==0)ret=max(ret,mx[r--]); l/=2; r/=2;
} return ret;
}
} T;
void init(signed N, std::vector<signed> H) {
n=N; h.resize(n); f0r(i,n)h[i]=H[i]; segtree S = segtree(n+1); FOR(i,1,n+1)S.update(i,-1); f0r(i,n){
L[i] = S.quermax(h[i],n); S.update(h[i],i);
} FOR(i,1,n+1)S.update(i,n); for(int i = n-1; i >= 0; i--){
R[i] = S.quermin(h[i],n); S.update(h[i],i);
}
T = segtree(n); f0r(i,n)T.update(i,h[i]); f0r(i,n){
if(L[i]==-1&&R[i]==n)a[i][0]=b[i][0]=-1; else if(L[i]==-1)a[i][0]=b[i][0]=R[i]; else if(R[i]==n)a[i][0]=b[i][0]=L[i];
else if(h[L[i]]>h[R[i]])a[i][0]=L[i],b[i][0]=R[i]; else a[i][0]=R[i],b[i][0]=L[i];
}
FOR(j,1,lg){
f0r(i,n){
if(a[i][j-1]==-1)a[i][j]=b[i][j]=-1; else{
a[i][j]=a[a[i][j-1]][j-1], b[i][j]=b[b[i][j-1]][j-1];
}
}
}
}
signed minimum_jumps(signed A, signed B, signed C, signed D) {
int s = A, t = C; if(T.quermax(s,t-1) > h[t])return -1;
int ans = 0, cur = s; for(int i = lg-1; i>=0; i--){
if(a[cur][i]!=-1&&h[a[cur][i]]<=h[t]){ans+=(1<<i),cur=a[cur][i];}
}
for(int i = lg-1; i>=0; i--){
if(b[cur][i]!=-1&&h[b[cur][i]]<=h[t])ans+=(1<<i),cur=b[cur][i];
} return ans;
}
