#include "jumps.h"
// #include <bits/stdc++.h>
#include <vector>
#include <cassert>
using namespace std;
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define f first
#define s second
const int N=200001, LG=18;
int lg[N];
int go[N][LG], goleft[N][LG], goright[N][LG];
int mx[N][LG];
int pos[N];
int n;
int h[N];
int get_max(int l, int r){
if(r<l) return 0;
int len=lg[r-l+1];
return max(mx[l][len], mx[r-(1<<len)+1][len]);
}
void init(int nn, std::vector<int> H) {
n=nn;
rep(i,2,n){
lg[i]=lg[i/2]+1;
}
rep(i,0,n-1){
mx[i][0]=H[i];
pos[H[i]]=i;
}
rep(j,1,lg[n]){
rep(i,0,n-(1<<j)){
mx[i][j]=max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
rep(i,0,n-1){
int ind=i;
for(int j=lg[n]; j>=0; j--){
if(ind-(1<<j)>=0 && get_max(ind-(1<<j), i)==H[i]) ind-=(1<<j);
}
goleft[i][0]=(ind==0?-1:H[ind-1]);
}
rep(i,0,n-1){
int ind=i;
for(int j=lg[n]; j>=0; j--){
if(ind+(1<<j)<n && get_max(i, ind+(1<<j))==H[i]) ind+=(1<<j);
}
goright[i][0]=(ind==n-1?-1:H[ind+1]);
}
rep(i,0,n-1){
go[i][0]=max(goleft[i][0], goright[i][0]);
}
rep(j,1,lg[n]){
rep(i,0,n-1){
goright[i][j]=(goright[i][j-1]==-1?-1:goright[pos[goright[i][j-1]]][j-1]);
go[i][j]=(go[i][j-1]==-1?-1:go[pos[go[i][j-1]]][j-1]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int mx=get_max(C, D);
if(get_max(B, C)>mx) return -1;
for(int j=lg[n]; j>=0; j--){
if(A+(1<<j)<=B && get_max(A+(1<<j), B)>mx) A+=(1<<j);
}
if(get_max(A, B)>mx) A++;
int ans=0;
int a=pos[get_max(A, B)];
int y=get_max(B+1, C-1);
for(int j=lg[n]; j>=0; j--){
if(go[a][j]>0 && go[a][j]<=y) ans+=(1<<j), a=pos[go[a][j]];
}
if(goright[a][0]!=-1 && pos[goright[a][0]]>=C) return ans+1;
if(goleft[a][0]!=-1 && goleft[a][0]<mx && goleft[a][0]>y) return ans+2;
for(int j=lg[n]; j>=0; j--){
if(goright[a][j]>0 && pos[goright[a][j]]<C) ans+=(1<<j), a=pos[goright[a][j]];
}
return ans+1;
}
//
