#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
struct SegmentTree {
vector<pair<int, int>> st;
int n;
SegmentTree() { }
void init(const vector<int> &v) {
n = v.size();
while (n & n - 1) ++n;
st.resize(n << 1, {0, 0});
for (int i = 0; i < v.size(); i++) {
st[i + n] = {v[i], i};
}
for (int i = n - 1; i > 0; i--) {
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
}
int find_last(int v, int l, int r, int ql, int qr, int x) {
if (l > qr || r < ql || st[v].first < x) return -1;
if (l >= ql && r <= qr) {
while (l < r) {
int m = l + r >> 1;
if (st[v << 1 | 1].first >= x) v = v << 1 | 1, l = m + 1;
else v <<= 1, r = m;
}
return l;
}
int m = l + r >> 1;
int k = find_last(v << 1 | 1, m + 1, r, ql, qr, x);
if (k != -1) return k;
return find_last(v << 1, l, m, ql, qr, x);
}
int qry(int l, int r) {
pair<int, int> mx = {0, 0};
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) mx = max(mx, st[l++]);
if (r & 1) mx = max(mx, st[--r]);
}
return mx.second;
}
int find_last(int l, int r, int x) {
return find_last(1, 0, n - 1, l, r, x);
}
} sgt;
const int N = 2e5, lg = 18, inf = 1e9;
int n, nxt[lg][N], prv[lg][N], g[lg][N], h[N];
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
sgt.init(H);
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 = 0; i < n; i++) {
if (nxt[0][i] == -1) g[0][i] = prv[0][i];
else if (prv[0][i] == -1) g[0][i] = nxt[0][i];
else g[0][i] = (h[nxt[0][i]] >= h[prv[0][i]] ? nxt[0][i] : prv[0][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]];
g[i][j] = g[i - 1][j] == -1 ? -1 : g[i - 1][g[i - 1][j]];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
int k = sgt.find_last(a, b, h[c]);
if (k == b) return -1;
b = sgt.qry((k == -1 ? a : k + 1), b);
int ans = 0;
for (int i = lg - 1; i >= 0; i--) {
if (g[i][b] != -1 && h[g[i][b]] < h[c]) {
b = g[i][b];
ans += (1 << i);
}
}
if (b > c) return -1;
for (int i = lg - 1; i >= 0; i--) {
if (nxt[i][b] != -1 && h[nxt[i][b]] <= h[c]) {
b = nxt[i][b];
ans += (1 << i);
}
}
return b == c ? ans : -1;
}
