#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'000 + 10,
MAX = 1'000'000,
LG = 17;
int n;
int h[MAXN];
int goL[MAXN], goR[MAXN];
int up[MAXN][LG + 1], upR[MAXN][LG + 1];
void init(int N, std::vector<int> H) {
n = N;
for (int i = 0; i < n; ++i) h[i] = H[i];
{ // go left
stack<int> st;
for (int i = 0; i < n; ++i) {
while (st.size() && h[st.top()] < h[i]) st.pop();
goL[i] = (st.size() ? st.top() : n);
st.push(i);
}
}
{ // go right
stack<int> st;
for (int i = n - 1; i >= 0; --i) {
while (st.size() && h[st.top()] < h[i]) st.pop();
goR[i] = (st.size() ? st.top() : n);
st.push(i);
}
}
h[n] = -1;
fill(up[n], up[n] + LG + 1, n);
for (int i = 0; i < n; ++i) {
up[i][0] = (h[goR[i]] > h[goL[i]] ? goR[i] : goL[i]);
}
h[n] = MAX;
fill(upR[n], upR[n] + LG + 1, n);
for (int i = 0; i < n; ++i) {
upR[i][0] = (h[goR[i]] < h[goL[i]] ? goR[i] : goL[i]);
}
for (int j = 1; j <= LG; ++j) {
for (int i = 0; i < n; ++i) {
up[i][j] = up[up[i][j - 1]][j - 1];
upR[i][j] = upR[upR[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ret = 0;
for (int j = LG; j >= 0; --j) {
if (h[up[A][j]] <= h[C]) {
ret += (1 << j);
A = up[A][j];
}
}
for (int j = LG; j >= 0; --j) {
if (h[upR[A][j]] <= h[C]) {
ret += (1 << j);
A = upR[A][j];
}
}
return A == C ? ret : -1;
}
