#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
static int n, LOG;
static vector<int> H;
static vector<vector<int>> upHigh, upLow;
void init(int N, vector<int> _H) {
n = N;
H = _H;
LOG = 1;
while ((1 << LOG) <= n) LOG++;
vector<int> L(n, -1), R(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && H[st.back()] < H[i]) {
st.pop_back();
}
if (!st.empty()) L[i] = st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && H[st.back()] < H[i]) {
st.pop_back();
}
if (!st.empty()) R[i] = st.back();
st.push_back(i);
}
vector<int> high(n, -1), low(n, -1);
for (int i = 0; i < n; i++) {
int a = L[i];
int b = R[i];
if (a == -1 && b == -1) {
continue;
} else if (a == -1) {
low[i] = b;
} else if (b == -1) {
low[i] = a;
} else {
if (H[a] > H[b]) {
high[i] = a;
low[i] = b;
} else {
high[i] = b;
low[i] = a;
}
}
}
upHigh.assign(LOG, vector<int>(n, -1));
upLow.assign(LOG, vector<int>(n, -1));
upHigh[0] = high;
upLow[0] = low;
for (int k = 1; k < LOG; k++) {
for (int i = 0; i < n; i++) {
int midHigh = upHigh[k - 1][i];
if (midHigh != -1) {
upHigh[k][i] = upHigh[k - 1][midHigh];
}
int midLow = upLow[k - 1][i];
if (midLow != -1) {
upLow[k][i] = upLow[k - 1][midLow];
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int s = A;
int t = C;
if (H[s] > H[t]) return -1;
int x = s;
int ans = 0;
for (int k = LOG - 1; k >= 0; k--) {
int y = upHigh[k][x];
if (y != -1 && H[y] <= H[t]) {
x = y;
ans += (1 << k);
}
}
if (x == t) return ans;
for (int k = LOG - 1; k >= 0; k--) {
int y = upLow[k][x];
if (y != -1 && H[y] < H[t]) {
x = y;
ans += (1 << k);
}
}
int y = upLow[0][x];
if (y == t) return ans + 1;
return -1;
}
