#include<bits/stdc++.h>
#include "jumps.h"
#define MAXN 200007
using namespace std;
int n,h[MAXN],pr[MAXN],nxt[MAXN];
stack<int> st;
int upleft[MAXN][20],upright[MAXN][20],up[MAXN][20];
void calcstack(){
st.push(0); pr[0]=0;
for(int i=1;i<=n;i++){
while(!st.empty() and h[i]>h[st.top()]){
st.pop();
}
pr[i]=st.top();
st.push(i);
}
while(!st.empty())st.pop();
st.push(n+1); nxt[n+1]=n+1;
for(int i=n;i>=1;i--){
while(!st.empty() and h[i]>h[st.top()]){
st.pop();
}
nxt[i]=st.top();
st.push(i);
}
}
int best(int x,int y){
if(h[x]>h[y])return x;
return y;
}
void calclift(){
for(int i=0;i<20;i++){
for(int f=0;f<=n+1;f++){
if(i==0){
upleft[f][0]=pr[f];
upright[f][0]=nxt[f];
up[f][0]=best(pr[f],nxt[f]);
}else{
upleft[f][i]=upleft[upleft[f][i-1]][i-1];
upright[f][i]=upright[upright[f][i-1]][i-1];
up[f][i]=up[up[f][i-1]][i-1];
}
}
}
}
void init(int N,vector<int> H){
n=N;
for(int i=1;i<=n;i++){
h[i]=H[i-1];
}
h[0]=h[n+1]=n+1;
calcstack();
calclift();
}
int minimum_jumps(int A, int B, int C, int D){
int ans=0;
A++; B++; C++; D++;
int maxs=C;
for(int i=19;i>=0;i--){
if(upright[maxs][i]<=D){
maxs=upright[maxs][i];
}
}
for(int i=19;i>=0;i--){
if(h[upleft[B][i]]<=h[maxs] and upleft[B][i]>=A){
B=upleft[B][i];
}
}
A=B;
for(int i=19;i>=0;i--){
if(h[up[A][i]]<=h[maxs] and upright[A][i]<C){
A=up[A][i];
ans+=(1<<i);
}
}
for(int i=19;i>=0;i--){
if(upright[A][i]<C){
A=upright[A][i];
ans+=(1<<i);
}
}
A=upright[A][0];
ans++;
if(A<C or A>D)return -1;
return ans;
}
/*int main(){
init(7, {3, 2, 1, 6, 4, 5, 7});
cout<<minimum_jumps(4, 4, 6, 6)<<"\n";
cout<<minimum_jumps(1, 3, 5, 6)<<"\n";
cout<<minimum_jumps(0, 1, 2, 2)<<"\n";
}*/
