#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int maxn = (int)2e5+10;
const int INF = (int)1e9;
bool increasing;
vector<int> adj[maxn];
int n, dis[maxn], pr[maxn], nx[maxn];
int bfs(int s1, int s2, int d1, int d2){
queue<int> Q;
while(!Q.empty()) Q.pop();
for(int i = 0; i < n; i++) dis[i]=INF;
for(int i = s1; i <= s2; i++) Q.push(i), dis[i]=0;
while(!Q.empty()){
int s = Q.front(); Q.pop();
if(d1<=s and s<=d2) return dis[s];
for(auto u : adj[s]){
if(dis[u]==INF){
dis[u] = dis[s]+1;
Q.push(u);
}
}
}
return -1;
}
void init(int N, vector<int> a) {
n = N; increasing = 1;
stack<pair<int,int>> S;
memset(pr,-1,sizeof(pr));
memset(nx,-1,sizeof(nx));
for(int i = 0; i < n; i++){
increasing&=(!i or a[i]>=a[i-1]);
while(!S.empty() and S.top().fi<a[i]) S.pop();
if(!S.empty()) pr[i] = S.top().se;
S.push({a[i],i});
}
while(!S.empty()) S.pop();
for(int i = n-1; i>=0; i--){
while(!S.empty() and S.top().fi<a[i]) S.pop();
if(!S.empty()) nx[i] = S.top().se;
S.push({a[i],i});
}
while(!S.empty()) S.pop();
for(int i = 0; i < n; i++){
if(pr[i]!=-1) adj[i].pb(pr[i]);
if(nx[i]!=-1) adj[i].pb(nx[i]);
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(increasing) return C-B;
return bfs(A,B,C,D);
}
