#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
using pi = pair<int, int>;
const int INF = 1e9+7, MB = 31;
int n;
V<int> h;
V<V<int>> fa, f1, f2;
void init(int N, V<int> H) {
n = N;
h = H;
V<int> st;
st = {};
fa = V<V<int>>(n, V<int>(2, -1));
for (int i = 0; i < n; i++) {
while (st.size() && h[st.back()] < h[i]) st.pop_back();
fa[i][0] = (st.size() ? st.back() : -1);
st.push_back(i);
}
st = {};
for (int i = n - 1; i >= 0; i--) {
while (st.size() && h[st.back()] < h[i]) st.pop_back();
fa[i][1] = (st.size() ? st.back() : -1);
st.push_back(i);
}
f1 = f2 = V<V<int>>(n, V<int>(MB + 1, -1));
for (int i = 0; i < n; i++) {
int fl = fa[i][0], fr = fa[i][1];
if (fl == -1) f1[i][0] = fr;
if (fr == -1) f1[i][0] = fl;
f1[i][0] = h[fl] > h[fr] ? fl : fr;
f2[i][0] = fr;
}
for (int j = 1; j <= MB; j++) {
for (int i = 0; i < n; i++) {
f1[i][j] = f1[i][j - 1] == -1 ? -1 : f1[f1[i][j - 1]][j - 1];
f2[i][j] = f2[i][j - 1] == -1 ? -1 : f2[f2[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (A == B && C == D) {
int x = A, res = 0;
for (int i = MB; i >= 0; i--) {
int f = f1[x][i];
if (f != -1 && h[f] <= h[C]) {
x = f;
res += (1 << i);
}
}
for (int i = MB; i >= 0; i--) {
int f = f2[x][i];
if (f != -1 && h[f] <= h[C] && f <= C) {
x = f;
res += (1 << i);
}
}
return (x == C ? res : -1);
}
V<int> d(n, -1);
queue<pi> q;
for (int i = A; i <= B; i++) {
q.push({i, 0});
}
while (!q.empty()) {
pi x = q.front();
q.pop();
if (x.first == -1) continue;
if (d[x.first] != -1) continue;
d[x.first] = x.second;
q.push({fa[x.first][0], x.second + 1});
q.push({fa[x.first][1], x.second + 1});
}
int ans = INF;
for (int i = C; i <= D; i++) {
if (d[i] != -1) {
ans = min(ans, d[i]);
}
}
return (ans == INF ? -1 : ans);
}
