#include "jumps.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2*1e5,MAXLG=18;
int lift[MAXLG][MAXN+1],lift2[MAXLG][MAXN+1],sparse[MAXLG][MAXN],loga[MAXN+1];
int le[MAXN+1],ri[MAXN+1];
vector<int> h;
int cmp(int i,int j){
if(h[i]>h[j]){
return i;
}
return j;
}
int query(int l,int r){
return cmp(sparse[loga[r-l+1]][l],sparse[loga[r-l+1]][r-(1<<loga[r-l+1])+1]);
}
void init(int n,vector<int> H){
loga[1]=0;
for(int i=2;i<=n;i++){
loga[i]=loga[i>>1]+1;
}
h=H;
le[n]=-1,ri[n]=n;
h.push_back(n+1);
stack<int> st;
for(int i=0;i<n;i++){
sparse[0][i]=i;
le[i]=-1;
while(!st.empty()&&h[st.top()]<h[i]){
st.pop();
}
if(!st.empty()){
le[i]=st.top();
}
st.push(i);
}
for(int i=1;i<MAXLG;i++){
for(int j=0;j+(1<<i)<=n;j++){
sparse[i][j]=cmp(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);
}
}
while(!st.empty()){
st.pop();
}
for(int i=n-1;i>=0;i--){
ri[i]=n;
while(!st.empty()&&h[st.top()]<h[i]){
st.pop();
}
if(!st.empty()){
ri[i]=st.top();
}
st.push(i);
}
lift[0][n]=n,lift2[0][n]=n;
for(int i=0;i<n;i++){
if(le[i]==-1&&ri[i]==n){
lift[0][i]=n,lift2[0][i]=n;
}
else if(le[i]==-1){
lift[0][i]=n,lift2[0][i]=ri[i];
}
else if(ri[i]==n){
lift[0][i]=n,lift2[0][i]=le[i];
}
else{
int idx1=le[i],idx2=ri[i];
if(h[idx1]<h[idx2]){
swap(idx1,idx2);
}
lift[0][i]=idx1,lift2[0][i]=idx2;
}
}
for(int i=1;i<MAXLG;i++){
for(int j=0;j<=n;j++){
lift[i][j]=lift[i-1][lift[i-1][j]];
lift2[i][j]=lift2[i-1][lift2[i-1][j]];
}
}
}
int minimum_jumps(int a, int b, int c, int d){
int low=a,high=b;
low--,high++;
int bst=query(c,d);
if(h[b]>h[bst]){
return -1;
}
while(high-low>1){
int mid=((high-low)>>1)+low;
int idx=query(mid,b);
if(h[idx]<h[bst]){
high=mid;
}
else{
low=mid;
}
}
a=query(high,b);
int ans=0;
if(ri[a]>=c){
return 1;
}
for(int i=MAXLG-1;i>=0;i--){
if(ri[lift[i][a]]<c){
ans+=(1<<i);
a=lift[i][a];
}
}
if(ri[lift[0][a]]<=d){
return ans+2;
}
for(int i=MAXLG-1;i>=0;i--){
if(ri[lift2[i][a]]<c){
ans+=(1<<i);
a=lift2[i][a];
}
}
ans++;
a=lift2[0][a];
if(ri[a]>d){
return -1;
}
return ans+1;
}
