#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];
int any[LOG][N];
int big[LOG][N];
int tor[LOG][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);
}
for(int i = 0 ; i < n; i ++ ){
if(lef[i] == -1 || rig[i] == -1)
any[0][i] = -1;
else{
big[0][i] = rig[i];
if(H[lef[i]] > H[rig[i]]){
any[0][i] = lef[i];
}
else{
any[0][i] = rig[i];
}
}
tor[0][i] = rig[i];
}
for(int i = 1; i < LOG; i ++ ){
for(int j = 0 ; j < n; j ++ ){
if(tor[i-1][j] == -1)
tor[i][j] = -1;
else
tor[i][j] = tor[i-1][tor[i-1][j]];
}
}
for(int i = 1 ; i < LOG; i ++ ){
for(int j = 0 ; j < n ; j ++ ){
if(any[i - 1][j] == -1){
any[i][j] = -1;
}
else{
big[i][j] = max(big[i-1][j], big[i-1][any[i-1][j]]);
any[i][j] = any[i-1][any[i-1][j]];
}
}
}
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;
for(int i = LOG - 1; i >= 0 ; i -- ){
if(any[i][B] == -1) continue;
if(big[i][B] >= C) continue;
if(H[any[i][B]] > chk.fi) continue;
B = any[i][B];
moves += (1 << i);
}
for(int i = LOG - 1; i >= 0 ; i -- ){
if(tor[i][B] == -1) continue;
if(tor[i][B] < C){
B = tor[i][B];
moves += (1 << i);
}
}
moves ++ ;
return moves;
}
