#include <bits/stdc++.h>
using namespace std;
int N;
int P[200005];
vector<int> ST[800005];
vector<int> adj[200005];
vector<int> H;
void build(int v, int l, int r) {
if(l == r) {
ST[v].push_back(P[l]);
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
int i = 0, j = 0;
while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
if(i == ST[v * 2].size())
ST[v].push_back(ST[v * 2 + 1][j++]);
else if(j == ST[v * 2 + 1].size())
ST[v].push_back(ST[v * 2][i++]);
else {
if(ST[v * 2][i] < ST[v * 2 + 1][j])
ST[v].push_back(ST[v * 2][i++]);
else ST[v].push_back(ST[v * 2 + 1][j++]);
}
}
}
int queryR(int v, int l, int r, int lo, int hi, int K) {
if(l > hi || r < lo) return 1e9 + 7;
if(l >= lo && r <= hi) {
int R = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
if(R == ST[v].size()) return 1e9 + 7;
return ST[v][R];
}
return min(queryR(v * 2, l, (l + r) / 2, lo, hi, K),
queryR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K));
}
int queryL(int v, int l, int r, int lo, int hi, int K) {
if(l > hi || r < lo) return -1;
if(l >= lo && r <= hi) {
int L = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
if(L == 0) return -1;
return ST[v][--L];
}
return max(queryL(v * 2, l, (l + r) / 2, lo, hi, K),
queryL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K));
}
void init(int _N, vector<int> _H) {
N = _N;
for(int l = 0; l < _N; l++) {
H.push_back(_H[l]);
P[_H[l]] = l;
}
build(1, 1, N);
for(int l = 0; l < _N; l++) {
int i = queryL(1, 1, N, _H[l] + 1, N, l);
int j = queryR(1, 1, N, _H[l] + 1, N, l);
if(i != -1) adj[l].push_back(i);
if(j != 1e9 + 7) adj[l].push_back(j);
}
}
int minimum_jumps(int A, int B, int C, int D) {
vector<int> dis(N, 1e9 + 7); priority_queue<pair<int, int>> Q;
for(int l = A; l <= B; l++) {
dis[l] = 0; Q.push({0, l});
}
while(!Q.empty()) {
pair<int, int> U = Q.top(); Q.pop();
if(-U.first > dis[U.second]) continue;
if(U.second >= C && U.second <= D) return -U.first;
for(auto V : adj[U.second]) {
if(dis[U.second] + 1 < dis[V]) {
dis[V] = dis[U.second] + 1;
Q.push({-dis[V], V});
}
}
}
return -1;
}
