#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)2e5 + 10;
const int LOG = 18;
int n;
vector<int> H;
pii tab[LOG][N];
int LG[N];
pii get(int lf, int rf){
int ag = LG[rf - lf + 1];
return max(tab[ag][lf], tab[ag][rf - (1 << ag) + 1]);
}
int lef[N];
int rig[N];
void init(int _N, vector<int> _H) {
n = _N;
H = _H;
for(int i = 0 ; i < n; i ++ ){
tab[0][i] = mp(H[i], i);
}
vector<int> ids;
for(int i = 0 ; i < n; i ++ ){
while(!ids.empty() && H[i] > H[ids.back()]){
ids.pop_back();
}
if(!ids.empty())
lef[i] = ids.back();
else
lef[i] = -1;
ids.push_back(i);
}
ids.clear();
for(int i = n - 1; i >= 0 ; i -- ){
while(!ids.empty() && H[i] > H[ids.back()]){
ids.pop_back();
}
if(!ids.empty())
rig[i] = ids.back();
else
rig[i] = -1;
ids.push_back(i);
}
int pak = 0;
for(int i = 1; i <= n; i ++ ){
while((1 << (pak + 1)) <= i){
pak ++ ;
}
LG[i] = pak;
}
for(int lg = 1; lg < LOG; lg ++ ){
for(int i = 0 ; i < n; i ++ ){
if(i + (1 << lg) - 1 < n){
tab[lg][i] = max(tab[lg-1][i], tab[lg-1][i + (1 << (lg - 1))]);
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
pii chk = get(C, D);
pii bins = get(B, C - 1);
if(bins.fi > chk.fi) return -1;
int cur = B;
int tr;
for(int go = LOG - 1; go >= 0 ; go -- ){
tr = cur - (1 << go);
if(tr >= A){
bins = get(tr, C - 1);
if(bins.fi < chk.fi)
cur = tr;
}
}
pii ash = get(cur, B);
B = ash.se;
int moves = 0;
while(1){
if(rig[B] >= C){
B = rig[B];
moves ++ ;
break;
}
if(lef[B] == -1 || H[lef[B]] > chk.fi) {
B = rig[B];
moves ++ ;
continue;
}
if(H[lef[B]] > H[rig[B]]){
B = lef[B];
moves ++ ;
}
else{
B = rig[B];
moves ++ ;
}
}
return moves;
}
