#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; vector<pair<int,int>> 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]=mp(x,k-n); 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]);
}
pair<int,int> quermin(int l, int r){
pair<int,int> ret = mp(4e18,-1); 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;
}
pair<int,int> quermax(int l, int r){
pair<int,int> ret = mp(-4e18,-1); 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).first; 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).first; 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]=R[i],b[i][0]=R[i]; else if(R[i]==n)a[i][0]=L[i],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]=-1; else{
a[i][j]=a[a[i][j-1]][j-1];
}
if(b[i][j-1]==-1)b[i][j]=-1; else b[i][j] = b[b[i][j-1]][j-1];
}
}
}
signed minimum_jumps(signed A, signed B, signed C, signed D) {
int s, t = C; int lo = A, hi = B+1; while(lo < hi){
int mid = lo + (hi-lo)/2; if(T.quermax(mid,B).first < h[t])hi=mid; else lo=mid+1;
} if(lo==B+1)return -1; pair<int,int>p = T.quermax(lo,B); if(p.first > h[t])return -1; s = p.second;
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];
} if(cur!=t)return -1; return ans;
}
