#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
vector<vector<int>> par_right, par_left;
vector<int> prv, nxt;
void init(int N, vector<int> H) {
par_right.assign(N, vector<int> (18, -1));
par_left.assign(N, vector<int> (18, -1));
prv.assign(N, -1);
nxt.assign(N, -1);
stack<int> st;
st.push(0);
for (int i = 1; i < N; i++) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
if (!st.empty())
prv[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
st.push(N - 1);
for (int i = N - 2; i >= 0; i--) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
if (!st.empty())
nxt[i] = st.top();
st.push(i);
}
for (int i = 0; i < N; i++) {
par_right[i][0] = nxt[i];
par_left[i][0] = prv[i];
}
for (int j = 1; j < 18; j++) {
for (int i = 0; i < N; i++) {
if (par_right[i][j - 1] != -1)
par_right[i][j] = par_right[par_right[i][j - 1]][j - 1];
if (par_left[i][j - 1] != -1)
par_left[i][j] = par_left[par_left[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (!(B < C || A > D)) return 0;
if (B < C) {
int ans = 0;
for (int i = 17; i > -1; i--) {
if (par_right[B][i] != -1 && par_right[B][i] < C) {
ans += 1 << i;
B = par_right[B][i];
}
}
assert(B < C);
if (nxt[B] != -1 && nxt[B] <= D)
return ans + 1;
return -1;
} else {
int ans = 0;
for (int i = 17; i > -1; i--) {
if (par_left[A][i] != -1 && par_left[A][i] > D) {
ans += 1 << i;
A = par_left[A][i];
}
}
assert(A > D);
if (prv[A] != -1 && prv[A] >= B)
return ans + 1;
return -1;
}
return 67;
}
