#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int BB = 20;
int lft[BB][maxn];
int rgt[BB][maxn];
int uly[BB][maxn];
int kici[BB][maxn];
void init(int N, vector<int> H) {
stack<int>S;
for(int i = 0;i < N;i++){
lft[0][i] = N;
while(!S.empty() and H[S.top()] < H[i]) S.pop();
if(!S.empty()) lft[0][i] = S.top();
S.push(i);
}
while(!S.empty()) S.pop();
for(int i = N-1;i >= 0;i--){
rgt[0][i] = N;
while(!S.empty() and H[S.top()] < H[i]) S.pop();
if(!S.empty()) rgt[0][i] = S.top();
S.push(i);
}
for(int i = 0;i < N;i++){
if(lft[0][i] == N and rgt[0][i] == N){
uly[0][i] = kici[0][i] = i;
continue;
}
if(lft[0][i] == N){
uly[0][i] = kici[0][i] = rgt[0][i];
}
else if(rgt[0][i] == N){
uly[0][i] = kici[0][i] = lft[0][i];
}
else {
if(H[lft[0][i]] > H[rgt[0][i]]){
uly[0][i] = lft[0][i];
kici[0][i] = rgt[0][i];
}
else {
uly[0][i] = rgt[0][i];
kici[0][i] = lft[0][i];
}
}
}
for(int i = 0;i < BB;i++) lft[i][N] = rgt[i][N] = N;
for(int i = 1;i < BB;i++){
for(int j = 0;j < N;j++){
lft[i][j] = lft[i-1][lft[i-1][j]];
rgt[i][j] = rgt[i-1][rgt[i-1][j]];
uly[i][j] = uly[i-1][uly[i-1][j]];
kici[i][j] = kici[i-1][kici[i-1][j]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(rgt[0][B] > D) return -1;
int x = B;
for(int i = BB-1;i >= 0;i--){
int nxt = lft[i][x];
if(nxt >= A and rgt[0][nxt] <= D) x = nxt;
}
// cout<<x<<'\n';
int ans = 0;
for(int i = BB-1;i >= 0;i--){
int nxt = uly[i][x];
if(rgt[0][nxt] < C){
x = nxt, ans += (1<<i);
}
}
// cout<<x<<'\n';
for(int i = BB-1;i >= 0;i--){
int nxt = rgt[i][x];
if(nxt < C) x = nxt, ans += (1<<i);
}
x = rgt[0][x],ans++;
if(x >= C and x <= D) return ans;
return -1;
}
