#include "jumps.h"
// author: yanybayev
// idea: KasymK
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int INF = 1e9 + 7;
const int LOG = 21;
const int N = 2e5 + 5;
int p[N][LOG];
int l[N][LOG];
int r[N][LOG];
vector<int> h;
void init(int N, vector<int> H) {
int n = N;
h = H;
h.pb(INF);
stack<int> st;
st.push(n);
for (int i = 0; i < n; ++ i) {
while (h[st.top()] < h[i]) st.pop();
l[i][0] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
st.push(n);
for (int i = n - 1; ~i; -- i) {
while (h[st.top()] < h[i]) st.pop();
r[i][0] = st.top();
st.push(i);
}
for (int i = 0; i < n; ++ i) {
int L = l[i][0];
int R = r[i][0];
if (h[L] > h[R]) p[i][0] = L;
else p[i][0] = R;
}
for (int k = 0; k < LOG; ++ k) {
l[n][k] = r[n][k] = p[n][k] = n;
}
for (int k = 1; k < LOG; ++ k) {
for (int i = 0; i <= n; ++ i) {
p[i][k] = p[p[i][k - 1]][k - 1];
l[i][k] = l[l[i][k - 1]][k - 1];
r[i][k] = r[r[i][k - 1]][k - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int x, y;
x = y = B;
for (int k = LOG - 1; ~k; -- k) {
if (r[x][k] < C) {
x = r[x][k];
}
}
if (r[x][0] > D) return -1;
for (int k = LOG - 1; ~k; -- k) {
if (l[y][k] >= A and h[l[y][k]] < h[x]) {
y = l[y][k];
}
}
int ans = 1;
for (int k = LOG - 1; ~k; -- k) {
if (h[p[y][k]] < h[x]) {
y = p[y][k];
ans += 1 << k;
}
}
int dirc = (r[l[y][0]][0] <= D ? ans + (l[y][0] < A) : INF);
for (int k = LOG - 1; ~k; -- k) {
if (r[y][k] <= x) {
y = r[y][k];
ans += 1 << k;
}
}
return min(dirc, ans);
}
