#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include <cassert>
#include "jumps.h"
#define SZ(x) (LL)(x.size())
#define FR(i,a,b) for(LL i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
typedef std::pair<LD,LD> PLD;
using namespace std;
const int MAXN=2e5+5, MAXLG=20;
int h[MAXN], l[MAXN], r[MAXN];
int hp[MAXN][MAXLG], rp[MAXN][MAXLG]; //high par, right par
int mx_hp[MAXN][MAXLG], mx_rp[MAXN][MAXLG];
int range[MAXN][MAXLG];
int n;
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
*/
void init(int N, std::vector<int> H) {
n=N;
FOR(i,n) h[i]=H[i];
deque<int> dq;
FOR(i,n){
while (!dq.empty () && h[dq.back()]<h[i]) dq.pop_back();
if (dq.empty()) l[i]=-1;
else l[i]=dq.back();
dq.push_back(i);
}
dq.clear();
for(int i=n-1;i>=0;i--){
while (!dq.empty () && h[dq.back()]<h[i]) dq.pop_back();
if (dq.empty()) r[i]=-1;
else r[i]=dq.back();
dq.push_back(i);
}
FOR(i,n){
if (l[i]==-1 && r[i]==-1) hp[i][0]=rp[i][0]=-1;
else if (r[i]==-1){
hp[i][0]=l[i];
rp[i][0]=-1;
}
else if (l[i]==-1) hp[i][0]=rp[i][0]=r[i];
else{
rp[i][0]=r[i];
if (h[l[i]]>h[r[i]]) hp[i][0]=l[i];
else hp[i][0]=r[i];
}
if (hp[i][0]!=-1) mx_hp[i][0]=max((int)i, hp[i][0]);
else mx_hp[i][0]=i;
if (rp[i][0]!=-1) mx_rp[i][0]=max((int)i, rp[i][0]);
else mx_rp[i][0]=i;
}
FR(j,1,MAXLG) FOR(i,n){
int p=rp[i][j-1];
if (p!=-1){
rp[i][j]=rp[p][j-1];
mx_rp[i][j]=max(mx_rp[p][j-1], mx_rp[i][j-1]);
}
else{
rp[i][j]=-1;
mx_rp[i][j]=mx_rp[i][j-1];
}
p=hp[i][j-1];
if (p!=-1){
hp[i][j]=hp[p][j-1];
mx_hp[i][j]=max(mx_hp[p][j-1], mx_hp[i][j-1]);
}
else{
hp[i][j]=-1;
mx_hp[i][j]=mx_hp[i][j-1];
}
}
FOR(i,n) range[i][0]=i;
FR(j,1,MAXLG) FOR(i,n){
if (i+(1<<(j-1))>=n) range[i][j]=range[i][j-1];
else if (h[range[i][j-1]]>h[range[i+(1<<(j-1))][j-1]]) range[i][j]=range[i][j-1];
else range[i][j]=range[i+(1<<(j-1))][j-1];
}
}
int query(int l, int r){
int j=(int)log2(r-l+1);
if (h[range[l][j]]>h[range[r-(1<<j)+1][j]]) return range[l][j];
else return range[r-(1<<j)+1][j];
}
int minimum_jumps(int a, int b, int c, int d) {
int mx=h[query(c,d)], ans=0;
if (h[b]>mx) return -1;
int lo=a, hi=b;
//find leftmost id s.t. h[id,id+1,...,b]<mx
while (lo<hi){
int mid=lo+(hi-lo)/2;
int id=query(mid,b);
if (h[id]<=mx) hi=mid;
else lo=mid+1;
}
int cur=query(lo,b);
int best=n;
bool can=false;
for (int j=MAXLG-1; j>=0; j--){
if (hp[cur][j]!=-1 && h[hp[cur][j]]<=mx){
if (mx_hp[cur][j]<c){
cur=hp[cur][j];
ans+=(1<<j);
}
else{
int tmp=cur;
int extra=0;
for(int k=j-1; k>=0; k--){
if(hp[tmp][k]!=-1 && mx_hp[tmp][k]<c){
tmp=hp[tmp][k];
extra+=(1<<k);
}
}
best=min(best, ans+extra+1);
can=true;
break;
}
}
}
//if (can) return best;
for (int j=MAXLG-1; j>=0; j--){
if (rp[cur][j]!=-1 && h[rp[cur][j]]<=mx){
if (mx_rp[cur][j]<c){
cur=rp[cur][j];
ans+=(1<<j);
}
else{
int tmp=cur;
int extra=0;
for(int k=j-1; k>=0; k--){
if(rp[tmp][k]!=-1 && mx_rp[tmp][k]<c){
tmp=rp[tmp][k];
extra+=(1<<k);
}
}
best=min(best, ans+extra+1);
can=true;
break;
}
}
}
if (can) return best;
return -1;
}
