#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
vector <int> L, R;
vector <vector<int>> G, T;
int n;
void init(int N, std::vector<int> H) {
n = N;
L.resize(n), R.resize(n);
G.resize(n), T.resize(n);
stack <int> stk;
stk.push(-1);
for ( int i = 0; i < n; i++ ){
while ( stk.size() > 1 && H[stk.top()] <= H[i] ){
stk.pop();
} L[i] = stk.top();
stk.push(i);
}
while ( stk.size() > 1 ) stk.pop();
for ( int i = n - 1; i >= 0; i-- ){
while ( stk.size() > 1 && H[stk.top()] <= H[i] ){
stk.pop();
} R[i] = stk.top();
stk.push(i);
}
for ( int i = 0; i < n; i++ ){
if ( L[i] == -1 && R[i] == -1 ){
continue;
}
if ( L[i] == -1 || (R[i] != -1 && H[L[i]] < H[R[i]]) ){
G[i].pb(R[i]);
} else G[i].pb(L[i]);
if ( L[i] != -1 ){
T[i].pb(L[i]);
}
if ( R[i] != -1 ){
T[i].pb(R[i]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if ( A == B && C == D && false ){
int u = A, v = C, ret = -1, cnt = 0;
do{
++cnt;
if ( R[u] == v ){
ret = cnt;
break;
}
if ( G[u].empty() ) break;
u = G[u].back();
} while ( true );
return ret;
}
vector <int> dp(n, n);
queue <int> q;
for ( int i = A; i <= B; i++ ){
dp[i] = 0;
q.push(i);
}
while ( !q.empty() ){
int u = q.front();
q.pop();
for ( auto &v: T[u] ){
if ( chmin(dp[v], dp[u] + 1) ){
q.push(v);
}
}
}
int opt = n;
for ( int i = C; i <= D; i++ ){
chmin(opt, dp[i]);
}
if ( opt == n ) opt = -1;
return opt;
}
