#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int lg = 18;
int st1[N][lg],st2[N][lg],dp[N][lg];
void init(int N, vector<int>H){
int n = N;
vector<int>h;
h.push_back(0);
for(int i = 0; i < H.size(); i++) h.push_back(H[i]);
stack<int>s;
for(int i = n; i >= 1; i--){
while(s.size() && h[s.top()] <= h[i]) s.pop();
if(s.size()) st2[i][0] = s.top();
s.push(i);
}
while(s.size()) s.pop();
for(int i = 1; i <= n; i++){
while(s.size() && h[s.top()] <= h[i]) s.pop();
if(s.size()) st1[i][0] = s.top();
s.push(i);
}
for(int i = 1; i <= n; i++){
if(h[st1[i][0]] > h[st2[i][0]]) dp[i][0] = st1[i][0];
else dp[i][0] = st2[i][0];
}
for(int j = 1; j < lg; j++){
for(int i = 1; i <= n; i++){
st1[i][j] = st1[st1[i][j-1]][j-1];
st2[i][j] = st2[st2[i][j-1]][j-1];
dp[i][j] = dp[dp[i][j-1]][j-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D){
int u = B;
for(int i = lg-1; i >= 0; i--){
if(st1[u][i] >= A && st2[st1[u][i]][0] <= D) u = st1[u][i];
}
int ans = 0;
for(int i = lg-1; i >= 0; i--){
if(dp[u][i] < C){
ans += (1 << i);
u = dp[u][i];
}
}
for(int i = lg-1; i >= 0; i--){
if(st2[u][i] < C){
u = st2[u][i];
ans += (1 << i);
}
}
if(st2[u][0] < C || st2[u][0] > D) return -1;
return ans+1;
}
