#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 2e5+5;
const int LG = 18;
int fir[N],lst[N];
int go1[N][LG];
int a[N],pos[N];
int n,q;
struct solver{
int fir[N],lst[N];
int go[N][LG];
int go1[N][LG];
int a[N],pos[N];
int n,q;
struct node{
int pos,mx;
}jump[N][LG];
struct segtree{
vector<pair<int,int>> st[4*N];
vector<int> mxsuf[4*N];
void build(int id,int l,int r,int a[]){
if(l == r){
st[id].push_back({a[l],l});
mxsuf[id].push_back(l);
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid,a);
build(id<<1|1,mid+1,r,a);
st[id]=st[id<<1];
for(auto v:st[id<<1|1]) st[id].push_back(v);
sort(st[id].begin(),st[id].end());
int mx=0;
for(int i=st[id].size()-1;i>=0;i--){
mx=max(mx,st[id][i].se);
mxsuf[id].push_back(mx);
}
reverse(mxsuf[id].begin(),mxsuf[id].end());
}
int getlast(int id,int l,int r,int u,int v,int val){
if(r<u || v<l) return 0;
if(u<=l && r<=v){
int t=upper_bound(st[id].begin(),st[id].end(),make_pair(val,0))-st[id].begin();
if(t<mxsuf[id].size()){
//cerr<<'.'<<' '<<st[id][t].se<<'\n';
return mxsuf[id][t];
}
else return 0;
}
int mid=(l+r)>>1;
return max(getlast(id<<1,l,mid,u,v,val),getlast(id<<1|1,mid+1,r,u,v,val));
}
int getmax(int id,int l,int r,int u,int v){
if(r<u || v<l) return 0;
if(u<=l && r<=v) return st[id].back().fi;
int mid=(l+r)>>1;
return max(getmax(id<<1,l,mid,u,v),getmax(id<<1|1,mid+1,r,u,v));
}
int get(int id,int l,int r,int u,int v,int val){
if(r<u || v<l) return 0;
if(u<=l && r<=v){
int t=lower_bound(st[id].begin(),st[id].end(),make_pair(val,0))-st[id].begin()-1;
if(t>=0) return st[id][t].fi;
else return 0;
}
int mid=(l+r)>>1;
return max(get(id<<1,l,mid,u,v,val),get(id<<1|1,mid+1,r,u,v,val));
}
}smt;
void init(int _n,vector<int> H){
n=_n;
for(int i=0;i<n;i++){
a[i+1]=H[i];
}
for(int i=1;i<=n;i++) pos[a[i]]=i;
a[0]=1e9;
smt.build(1,1,n,a);
//
vector<int> st;
for(int i=1;i<=n;i++){
while(!st.empty() && a[st.back()] < a[i]) st.pop_back();
if(st.size()) fir[i]=st.back();
else fir[i]=0;
st.push_back(i);
}
st.clear();
for(int i=n;i>=1;i--){
while(!st.empty() && a[st.back()] < a[i]) st.pop_back();
if(st.size()) lst[i]=st.back();
else lst[i]=0;
st.push_back(i);
}
for(int i=1;i<=n;i++){
if(!fir[i] && !lst[i]){
jump[i][0]={(int)1e9,(int)1e9};
}
else if(!fir[i]){
jump[i][0]={lst[i],max(i,lst[i])};
}else if(!lst[i]){
jump[i][0]={fir[i],max(i,fir[i])};
}else{
if(a[fir[i]] > a[lst[i]]) jump[i][0]={fir[i],max(i,fir[i])};
else jump[i][0]={lst[i],max(i,lst[i])};
}
go[i][0]=lst[i];
go1[i][0]=fir[i];
if(go1[i][0] == 0) go1[i][0]=1e9;
if(go[i][0] == 0) go[i][0]=1e9;
}
for(int lg=1;lg<LG;lg++){
for(int i=1;i<=n;i++){
if(go[i][lg-1] == 1e9) go[i][lg]=1e9;
else{
go[i][lg]=go[go[i][lg-1]][lg-1];
}
}
for(int i=1;i<=n;i++){
if(go1[i][lg-1] == 1e9) go1[i][lg]=1e9;
else{
go1[i][lg]=go1[go1[i][lg-1]][lg-1];
}
}
for(int i=1;i<=n;i++){
if(jump[i][lg-1].pos == (int)1e9) jump[i][lg]={(int)1e9,(int)1e9};
else{
jump[i][lg].pos=jump[jump[i][lg-1].pos][lg-1].pos;
jump[i][lg].mx=max(jump[i][lg-1].mx,jump[jump[i][lg-1].pos][lg-1].mx);
}
}
}
}
int minj(int l,int r,int u,int v){
int maxuv=smt.getmax(1,1,n,u,v);
int b=smt.getlast(1,1,n,l,r,maxuv);
b++;
b=max(b,l);
// cerr<<'\n';
if(b>r) return 1e9;
int sta=smt.get(1,1,n,b,r,maxuv);
sta=pos[sta];
int lim=0;
int p=sta;
for(int lg=LG-1;lg>=0;lg--){
if(jump[p][lg].pos > n || jump[p][lg].pos < 1) continue;
if(a[jump[p][lg].pos] < maxuv){
p=jump[p][lg].pos;
lim += (1<<lg);
}
}
int num=0;
p=sta;
for(int lg=LG-1;lg>=0;lg--){
if(num+(1<<lg) <= lim){
if(jump[p][lg].mx < u){
p=jump[p][lg].pos;
num += (1<<lg);
}
}
}
for(int lg=LG-1;lg>=0;lg--){
if(go[p][lg] < u){
p=go[p][lg];
num += (1<<lg);
}
}
num++;
p=go[p][0];
if(u <= p && p <= v){
return num;
}else return 1e9;
}
}slv1,slv2;
void init(int _n,vector<int> H){
n=_n;
for(int i=0;i<n;i++){
a[i+1]=H[i];
}
for(int i=1;i<=n;i++) pos[a[i]]=i;
vector<int> st;
for(int i=1;i<=n;i++){
while(!st.empty() && a[st.back()] < a[i]) st.pop_back();
if(st.size()) fir[i]=st.back();
else fir[i]=0;
st.push_back(i);
}
st.clear();
for(int i=n;i>=1;i--){
while(!st.empty() && a[st.back()] < a[i]) st.pop_back();
if(st.size()) lst[i]=st.back();
else lst[i]=0;
st.push_back(i);
}
for(int i=1;i<=n;i++){
go1[i][0]=fir[i];
if(go1[i][0] == 0) go1[i][0]=1e9;
}
for(int lg=1;lg<LG;lg++){
for(int i=1;i<=n;i++){
if(go1[i][lg-1] == 1e9) go1[i][lg]=1e9;
else{
go1[i][lg]=go1[go1[i][lg-1]][lg-1];
}
}
}
slv1.init(n,H);
reverse(H.begin(),H.end());
slv2.init(n,H);
}
int minimum_jumps(int l,int r,int u,int v){
int ans=1e9;
++l;++r;++u;++v;
int maxuv=slv1.smt.getmax(1,1,n,u,v);
int b=slv1.smt.getlast(1,1,n,l,r,maxuv);
b++;
b=max(b,l);
// cerr<<'\n';
if(b>r) return -1;
int sta=slv1.smt.get(1,1,n,b,r,maxuv);
sta=pos[sta];
if(sta+1 >= u) return 1;
int mxv=slv1.smt.getmax(1,1,n,sta+1,u-1);
if(mxv > maxuv) return -1;
if(a[sta] > mxv) return 1;
int pv=pos[mxv];
ans=min(ans,slv1.minj(sta,sta,pv,pv)+1);
int p=sta;
for(int lg=LG-1;lg>=0;lg--){
if(go1[p][lg] == 1e9) continue;
if(a[go1[p][lg]] < mxv){
p=go1[p][lg];
}
}
p=go1[p][0];
if(1 <= p && p <= n && a[p] > mxv && a[p] < maxuv){
ans=min(ans,slv2.minj(n-sta+1,n-sta+1,n-p+1,n-p+1)+1);
}
}
//signed main(){
// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// if(fopen("text.inp","r")){
// //freopen("text.inp","r",stdin);
// }
// init(7, {2,3,6,1,4,5,7});
// cout<<minimum_jumps(1,3,4,5)<<'\n';
//}
