#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> R[18], L[18], U[18];
void init(int N, std::vector<int> H) {
for (int i = 0; i < 18; i++){
R[i].resize(N);
L[i].resize(N);
U[i].resize(N);
}
stack<int> st;
for (int i = 0; i < N; i++){
while (st.size() && H[st.top()] < H[i]){
st.pop();
}
if (st.empty()) L[0][i] = -1;
else L[0][i] = st.top();
st.push(i);
}
while (st.size()) st.pop();
for (int i = N-1; i >= 0; i--){
while (st.size() && H[st.top()] < H[i]){
st.pop();
}
if (st.empty()) R[0][i] = -1;
else R[0][i] = st.top();
st.push(i);
}
for (int i = 0; i < N; i++){
if (L[0][i] == -1) U[0][i] = R[0][i];
else if (R[0][i] == -1) U[0][i] = L[0][i];
else U[0][i] = H[L[0][i]] > H[R[0][i]] ? L[0][i] : R[0][i];
}
for (int k = 1; k < 18; k++){
for (int i = 0; i < N; i++){
if (U[k-1][i] == -1) U[k][i] = -1;
else U[k][i] = U[k-1][U[k-1][i]];
if (L[k-1][i] == -1) L[k][i] = -1;
else L[k][i] = L[k-1][L[k-1][i]];
if (R[k-1][i] == -1) R[k][i] = -1;
else R[k][i] = R[k-1][R[k-1][i]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int s = B;
for (int k = 17; k >= 0; k--){
if (L[k][s] != -1 && L[k][s] >= A && R[0][L[k][s]] != -1 && R[0][L[k][s]] <= D){
s = L[k][s];
}
}
int ans = 0;
for (int k = 17; k >= 0; k--){
if (U[k][s] != -1 && R[0][U[k][s]] != -1 && R[0][U[k][s]] < C){
s = U[k][s];
ans += (1<<k);
}
}
if (U[0][s] != -1 && R[0][s] != -1 && R[0][s] < C && R[0][U[0][s]] != -1 && R[0][U[0][s]] <= D){
ans++;
s = U[0][s];
}
for (int k = 17; k >= 0; k--){
if (R[k][s] != -1 && R[k][s] < C){
s = R[k][s];
ans += (1<<k);
}
}
if (R[0][s] == -1 || R[0][s] > D) return -1;
return ans + 1;
}
