#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int h[MAXN], prevmx[MAXN], nxtmx[MAXN], idx[MAXN];
int n;
struct segtree {
int n;
vector<pair<int, int>> seg;
segtree() = default;
segtree(int n) : n(n), seg(2 * n, {-1, -1}) {};
void update(int i, pair<int, int> val) {
i += n;
seg[i] = max(seg[i], val);
for (; i >>= 1;) {
seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
}
pair<int, int> query(int l, int r) {
pair<int, int> ans = {-1, -1};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
ans = max(ans, seg[l++]);
}
if (r & 1) {
ans = max(ans, seg[--r]);
}
}
return ans;
}
};
segtree st;
void init(int N, vector<int> H) {
n = N;
st = n;
copy(H.begin(), H.end(), h);
for (int i = 0; i < n; ++i) {
idx[--h[i]] = i;
st.update(i, {h[i], i});
}
for (int i = 0; i < n; ++i) {
prevmx[i] = i - 1;
while (prevmx[i] != -1 && h[prevmx[i]] <= h[i]) {
prevmx[i] = prevmx[prevmx[i]];
}
}
for (int i = n - 1; i >= 0; --i) {
nxtmx[i] = i + 1;
while (nxtmx[i] < n && h[nxtmx[i]] <= h[i]) {
nxtmx[i] = nxtmx[nxtmx[i]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
queue<int> q;
vector<bool> visited(n);
for (int i = A; i <= B; ++i) {
q.push(i);
visited[i] = true;
}
int dist = 0;
while (!q.empty()) {
int sz = q.size();
for (int k = 0; k < sz; ++k) {
int cur = q.front();
q.pop();
if (C <= cur && cur <= D) {
return dist;
}
if (prevmx[cur] != -1 && !visited[prevmx[cur]]) {
q.push(prevmx[cur]);
visited[prevmx[cur]] = true;
}
if (nxtmx[cur] < n && !visited[nxtmx[cur]]) {
q.push(nxtmx[cur]);
visited[nxtmx[cur]] = true;
}
}
dist++;
}
return -1;
}
#ifndef EVAL
int main() {
init(7, {7, 1, 4, 2, 3, 5, 6});
cout << minimum_jumps(1, 4, 5, 6) << '\n';
cout << minimum_jumps(1, 3, 4, 6) << '\n';
cout << minimum_jumps(0, 1, 2, 2) << '\n';
return 0;
}
#endif
