#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;
const ll inf=1e18;
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 up3[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;
up3[i][0]=-1;
up2[i][0]=-1;
}
else if(f==-1){
up1[i][0]=s;
up3[i][0]=s;
up2[i][0]=-1;
}
else if(s==-1){
up1[i][0]=f;
up3[i][0]=f;
up2[i][0]=-1;
}
else{
if(h[f]>h[s]){
up1[i][0]=f;
up3[i][0]=f;
up2[i][0]=s;
}
else{
up1[i][0]=s;
up3[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];
if(up3[up1[i][j-1]][j-1]==-1){
up3[i][j]=-1;
}
else{
up3[i][j]=max(up3[i][j-1], up3[up1[i][j-1]][j-1]);
}
}
else{
up1[i][j]=-1;
up3[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(0, b, mx);
// cout<<"tep: "<<tep<<'\n';
if(tep==b){
return -1;
}
ll f, s;
if(tep==-1){
tep=0;
}
else{
tep++;
}
ll mx2=rmax(max(tep, a), b);
f=id[mx2];
ll mx3=rmax(tep, c-1);
s=f1(c, d, mx3);
if(s==-1){
return -1;
}
ll re=inf;
// for(ll tar=c;tar<=d;tar++){
ll mxidx=f;
ll ans=0;
ll cur=f;
ll cnt=0;
for(ll i=LOG-1;i>=0;i--){
if(up1[cur][i]==-1) continue;
if(h[up1[cur][i]]<=h[s]){
// mxidx=max(mxidx, up3[cur][i]);
cur=up1[cur][i];
ans+=(1LL<<i);
cnt+=(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);
}
}
cnt--;
cur=f;
for(ll i=0;i<LOG;i++){
if(cnt&(1LL<<i)){
mxidx=max(mxidx, up3[cur][i]);
cur=up1[cur][i];
}
}
// cout<<mxidx<<'\n';
auto check=[&](ll tar){
ll dumb=f;
for(ll i=0;i<LOG;i++){
if(tar&(1LL<<i)){
if(up1[dumb][i]==-1) return false;
dumb=up1[dumb][i];
}
}
if(up2[dumb][0]>=c && up2[dumb][0]<=d){
return true;
}
return false;
};
ll lef=0, rig=ans-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(check(mid)){
ans=mid+1;
rig=mid-1;
}
else{
lef=mid+1;
}
}
ll dumb2=rmax(mxidx, c-1);
ll s2=f1(c, d, dumb2);
if(s2!=-1){
ll ans2=0;
cur=f;
for(ll i=LOG-1;i>=0;i--){
if(up1[cur][i]==-1) continue;
if(h[up1[cur][i]]<=h[s2]){
// mxidxax(mxidx, up3[cur][i]);
cur=up1[cur][i];
ans2+=(1LL<<i);
}
}
for(ll i=LOG-1;i>=0;i--){
if(up2[cur][i]==-1) continue;
if(h[up2[cur][i]]<=h[s2]){
cur=up2[cur][i];
ans2+=(1LL<<i);
}
}
ans=min(ans, ans2);
}
return (int) ans;
}
