#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);
int rng() {
return ui(mrand);
}
const int N=200200;
vector<int> radj[N];
vector<int> adjS[N];
int n;
bool special[N];
int l[N],r[N];
int dl[N],dr[N];
int out[N];
const int inf=1e9;
void init(int _N,vector<int> H) {
int Max = 0;
n=_N;
for (int i=0;i<n;i++) if (cmax(Max,H[i]))
special[i]=1;
Max=0;
for (int i=n-1;i>=0;i--) if (cmax(Max,H[i]))
special[i]=1;
vector<int> stk;
for (int i=0;i<n;i++) {
while(!stk.empty() && H[stk.back()] < H[i]) stk.pop_back();
if (!stk.empty()) {
if (special[i]) {
assert(special[stk.back()]);
adjS[i].push_back(stk.back());
} else {
radj[stk.back()].push_back(i);
out[i]++;
}
}
stk.push_back(i);
}
stk.clear();
for (int i=n-1;i>=0;i--) {
while(!stk.empty() && H[stk.back()] < H[i]) stk.pop_back();
if (!stk.empty()) {
if (special[i]) {
assert(special[stk.back()]);
adjS[i].push_back(stk.back());
} else {
radj[stk.back()].push_back(i);
out[i]++;
}
}
stk.push_back(i);
}
for (int i=0;i<n;i++) {
l[i]=r[i]=(special[i]?i:-1);
dl[i]=dr[i]=(special[i]?0:inf);
}
stk.clear();
for (int i=0;i<n;i++) if (out[i]==0) {
assert(special[i]);
stk.push_back(i);
}
for (int i=0;i<stk.size();i++) {
int u=stk[i];
for (int &v: radj[u]) {
if (special[u]) {
if (v > u) {
l[v]=l[u];
dl[v]=1;
} else {
r[v]=r[u];
dr[v]=1;
}
} else {
l[v]=l[u],r[v]=r[u];
cmin(dl[v],dl[u]+1),cmin(dr[v],dr[u]+1);
}
if (--out[v] == 0) {
stk.push_back(v);
}
}
}
// for (int i=0;i<n;i++) {
// cout << l[i] << " " << r[i] << " " << dl[i] << " " << dr[i] << endl;
// }
}
int walk(int u,int c,int d) {
if (u == -1) return inf;
assert(special[u]);
if (c <= u && u <= d) return 0;
int ans = inf;
for (int &v: adjS[u])
cmin(ans,walk(v,c,d)+1);
return ans;
}
int minimum_jumps(int a,int b,int c,int d) {
int ans=inf;
for (int i=a,j=a;i<=b;i=j) {
int min1=inf,min2=inf;
while(j<=b && dl[i]==dl[j]) {
cmin(min1,dl[j]),cmin(min2,dr[j]);
j++;
}
cmin(ans,min(min1+walk(l[i],c,d),min2+walk(r[i],c,d)));
}
return (ans==inf?-1:ans);
}
