#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 200000;
const int Log = 18;
int N;
int low[MaxN][Log], high[MaxN][Log];
int lf[MaxN][Log], rg[MaxN][Log];
int rmq[MaxN][Log];
vector<int> H;
void init(int _N, vector<int> _H) {
N = _N, H = _H;
stack<int> st;
for (int i = 0; i < N; i++){
while (!st.empty() && H[st.top()] < H[i]) st.pop();
lf[i][0] = (st.empty() ? -1 : st.top());
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = N - 1; i >= 0; i--){
while (!st.empty() && H[st.top()] < H[i]) st.pop();
rg[i][0] = (st.empty() ? -1 : st.top());
st.push(i);
}
memset(low, -1, sizeof(low));
memset(high, -1, sizeof(high));
for (int i = 0; i < N; i++){
int l = lf[i][0], r = rg[i][0];
if (l == -1 && r == -1) continue;
if (l != -1 && r != -1){
low[i][0] = (H[l] < H[r] ? l : r);
high[i][0] = (H[l] > H[r] ? l : r);
} else {
low[i][0] = high[i][0] = (l != -1 ? l : r);
}
}
for (int j = 1; j < Log; j++){
for (int i = 0; i < N; i++){
if (low[i][j - 1] != -1){
low[i][j] = low[low[i][j - 1]][j - 1];
}
if (high[i][j - 1] != -1){
high[i][j] = high[high[i][j - 1]][j - 1];
}
if (lf[i][j - 1] != -1){
lf[i][j] = lf[lf[i][j - 1]][j - 1];
} else {
lf[i][j] = -1;
}
if (rg[i][j - 1] != -1){
rg[i][j] = rg[rg[i][j - 1]][j - 1];
} else {
rg[i][j] = -1;
}
}
}
for (int i = 0; i < N; i++) rmq[i][0] = H[i];
for (int j = 1; j < Log; j++){
for (int i = 0; i + (1 << j) - 1 < N; i++){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int z = 31 - __builtin_clz(D - C + 1);
int mx = max(rmq[C][z], rmq[D - (1 << z) + 1][z]);
int ans = 0;
int v = B;
for (int i = Log - 1; i >= 0; i--){
int u = lf[v][i];
if (u != -1 && u >= A && H[u] <= mx) v = u;
}
for (int i = Log - 1; i >= 0; i--){
int u = high[v][i];
if (u != -1 && u <= D && H[u] <= mx){
ans += 1 << i;
v = u;
}
}
for (int i = Log - 1; i >= 0; i--){
int u = rg[v][i];
if (u != -1 && u < C){
ans += 1 << i;
v = u;
}
}
if (v < C){
v = rg[v][0];
ans++;
}
return (C <= v && v <= D ? ans : -1);
}
