#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
const int N = 2e5, lg = 18, inf = 1e9;
int n, nxt[lg][N], prv[lg][N], h[N];
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
stack<int> st;
for (int i = 0; i < n; i++) {
while (st.size() && h[st.top()] <= h[i]) st.pop();
prv[0][i] = st.size() ? st.top() : -1;
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();
nxt[0][i] = st.size() ? st.top() : -1;
st.push(i);
}
for (int i = 1; i < lg; i++) {
for (int j = 0; j < n; j++) {
prv[i][j] = prv[i - 1][j] == -1 ? -1 : prv[i - 1][prv[i - 1][j]];
nxt[i][j] = nxt[i - 1][j] == -1 ? -1 : nxt[i - 1][nxt[i - 1][j]];
}
}
}
int f(int i, int tl, int ti) {
for (int j = 0; j < lg; j++) {
if (tl >> j & 1) {
i = prv[j][i];
}
if (i == -1) return inf;
}
int ans = tl;
for (int j = lg - 1; j >= 0; j--) {
if (nxt[j][i] != -1 && h[nxt[j][i]] <= h[ti]) {
ans += (1 << j);
i = nxt[j][i];
}
}
return i == ti ? ans : inf;
}
int minimum_jumps(int a, int b, int c, int d) {
int l = 0, r = n;
while (l < r) {
int m = l + r >> 1;
if (f(b, m, c) == inf) r = m;
else l = m + 1;
}
r = l - 1;
l = 0;
while (l < r) {
int m = l + r >> 1;
if (f(b, m, c) > f(b, m + 1, c)) l = m + 1;
else r = m;
}
int ans = f(b, l, c);
return ans == inf ? -1 : ans;
}
