#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 16;
const int MLOG = 21;
int arr[MAXN],spRight[MLOG][MAXN],spLeft[MLOG][MAXN],spBest[MLOG][MAXN];
void init(int N,vector<int> H){
arr[0] = arr[N+1] = N+8;
for(int i=1;i<=N;i++){
arr[i] = H[i-1];
}
stack<int> stkRight,stkLeft;
for(int i=0;i<=N+1;i++){
while((!stkRight.empty()) && arr[stkRight.top()] <= arr[i]){
spRight[0][stkRight.top()] = i;
stkRight.pop();
}
stkRight.push(i);
}
spRight[0][N+1] = N+1;
for(int i=N+1;i>=0;i--){
while((!stkLeft.empty()) && arr[stkLeft.top()] <= arr[i]){
spLeft[0][stkLeft.top()] = i;
stkLeft.pop();
}
stkLeft.push(i);
}
spLeft[0][0] = 0;
for(int i=0;i<=N+1;i++){
if(arr[spLeft[0][i]] > arr[spRight[0][i]]){
spBest[0][i] = spLeft[0][i];
}else{
spBest[0][i] = spRight[0][i];
}
}
for(int i=1;i<MLOG;i++){
for(int j=0;j<=N+1;j++){
spLeft[i][j] = spLeft[i-1][spLeft[i-1][j]];
spRight[i][j] = spRight[i-1][spRight[i-1][j]];
spBest[i][j] = spBest[i-1][spBest[i-1][j]];
}
}
}
int minRight(int idx,int C,int D){
int res = 1;
for(int i=MLOG;i>0;i--){
if(spRight[i-1][idx] < C){
idx = spRight[i-1][idx];
res += (1 << (i-1));
}
}
idx = spRight[0][idx];
return (idx > D ? -1 : res);
}
int minimum_jumps(int A,int B,int C,int D){
A++,B++,C++,D++;
int curr = B;
for(int i=MLOG;i>0;i--){
if(spLeft[i-1][curr] >= A && spRight[0][spLeft[i-1][curr]] <= D){
curr = spLeft[i-1][curr];
}
}
int spSum = 0;
for(int i=MLOG;i>0;i--){
if(spRight[0][spBest[i-1][curr]] < C){
curr = spBest[i-1][curr];
spSum += (1 << (i-1));
}
}
int res = MAXN;
if(minRight(curr,C,D) != -1){
res = min(res,minRight(curr,C,D)+spSum);
}
curr = spBest[0][curr];
if(minRight(curr,C,D) != -1){
res = min(res,minRight(curr,C,D)+spSum+1);
}
return (res == MAXN ? -1 : res);
}
