#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=2e5+5;
const ll LOG=20;
ll n;
ll h[mxN];
ll id[mxN];
ll rmq1[mxN][LOG];
ll rmq2[mxN][LOG];
ll up1[mxN][LOG];
ll up2[mxN][LOG];
ll rmax(ll a, ll b){
ll lg=31-__builtin_clz(b-a+1);
return max(rmq1[a][lg], rmq1[b-(1LL<<lg)+1][lg]);
}
ll rmin(ll a, ll b){
ll lg=31-__builtin_clz(b-a+1);
return min(rmq2[a][lg], rmq2[b-(1LL<<lg)+1][lg]);
}
ll f1(ll a, ll b, ll val){
ll lef=a, rig=b;
ll re=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(rmax(a, mid)>=val){
re=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
return re;
}
ll f2(ll a, ll b, ll val){
ll lef=a, rig=b;
ll re=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(rmax(mid, b)>=val){
re=mid;
lef=mid+1;
}
else{
rig=mid-1;
}
}
return re;
}
}
void init(int N, std::vector<int> H) {
n=N;
for(ll i=0;i<n;i++){
h[i]=H[i]-1;
id[h[i]]=i;
}
for(ll i=0;i<n;i++){
rmq1[i][0]=h[i];
rmq2[i][0]=h[i];
}
for(ll j=1;j<LOG;j++){
for(ll i=0;i+(1LL<<j)-1<n;i++){
rmq1[i][j]=max(rmq1[i][j-1], rmq1[i+(1LL<<(j-1))][j-1]);
rmq2[i][j]=min(rmq2[i][j-1], rmq2[i+(1LL<<(j-1))][j-1]);
}
}
for(ll i=0;i<n;i++){
ll f=f1(i+1, n-1, h[i]);
ll s=f2(0, i-1, h[i]);
if(f==-1 && s==-1){
up1[i][0]=-1;
up2[i][0]=-1;
}
else if(f==-1){
up1[i][0]=s;
up2[i][0]=-1;
}
else if(s==-1){
up1[i][0]=f;
up2[i][0]=-1;
}
else{
if(h[f]>h[s]){
up1[i][0]=f;
up2[i][0]=s;
}
else{
up1[i][0]=s;
up2[i][0]=f;
}
}
// cout<<i<<' '<<up1[i][0]<<' '<<up2[i][0]<<'\n';
}
for(ll j=1;j<LOG;j++){
for(ll i=0;i<n;i++){
if(up1[i][j-1]!=-1) up1[i][j]=up1[up1[i][j-1]][j-1];
else up1[i][j]=-1;
if(up2[i][j-1]!=-1) up2[i][j]=up2[up2[i][j-1]][j-1];
else up2[i][j]=-1;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
ll a=A;
ll b=B;
ll c=C;
ll d=D;
ll mx=rmax(c, d);
// cout<<"mx: "<<mx<<'\n';
ll tep=f2(a, b, mx);
// cout<<"tep: "<<tep<<'\n';
if(tep==b){
return -1;
}
ll f, s;
if(tep==-1){
tep=a;
}
else{
tep++;
}
ll mx2=rmax(tep, b);
f=id[mx2];
ll mx3=rmax(tep, c-1);
s=f1(c, d, mx3);
if(s==-1){
return -1;
}
ll ans=0;
ll cur=f;
for(ll i=LOG-1;i>=0;i--){
if(up1[cur][i]==-1) continue;
if(h[up1[cur][i]]<=h[s]){
cur=up1[cur][i];
ans+=(1LL<<i);
}
}
for(ll i=LOG-1;i>=0;i--){
if(up2[cur][i]==-1) continue;
if(h[up2[cur][i]]<=h[s]){
cur=up2[cur][i];
ans+=(1LL<<i);
}
}
return (int) ans;
}
