#include "jumps.h"
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,a[maxN],l[maxN],r[maxN];
pli st[4*maxN];
void upd(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id]={val,pos};
return;
}
ll mid=l+r>>1;
if(pos<=mid) upd(pos,val,id*2,l,mid);
else upd(pos,val,id*2+1,mid+1,r);
st[id]=max(st[id*2],st[id*2+1]);
}
pli get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
if(j<l||r<i) return {0,0};
if(i<=l&&r<=j) return st[id];
ll mid=l+r>>1;
return max(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
vector<ll>g[maxN];
ll d[maxN];
void dfs(ll u)
{
for(int v:g[u])
{
d[v]=d[u]+1;
dfs(v);
}
}
int par[maxN][18],nxt[maxN][18];
void init(int N,vector<int> H)
{
n=N;
for(int i=1;i<=n;i++) a[i]=H[i-1],upd(i,a[i]);
vector<int>dq;
a[0]=inf;
for(int i=1;i<=n;i++)
{
while(!dq.empty()&&a[i]>a[dq.back()]) dq.pop_back();
if(dq.size()==0) l[i]=0;
else l[i]=dq.back();
dq.pb(i);
}
dq.clear();
ll rr=0;
for(int i=n;i>=1;i--)
{
while(!dq.empty()&&a[i]>a[dq.back()]) dq.pop_back();
if(dq.size()==0) r[i]=0;
else r[i]=dq.back();
dq.pb(i);
if(l[i]==0&&r[i]==0) rr=i;
}
for(int i=1;i<=n;i++)
{
bool sw=0;
if(a[l[i]]>a[r[i]]) swap(l[i],r[i]),sw=true;
g[l[i]].pb(i);
par[i][0]=r[i]==0?l[i]:r[i];
if(sw) swap(l[i],r[i]);
nxt[i][0]=r[i];
if(r[i]==0) nxt[i][0]=n+1;
}
dfs(rr);
for(int j=1;j<=17;j++)
{
for(int i=1;i<=n;i++)
{
par[i][j]=par[par[i][j-1]][j-1];
if(nxt[i][j-1]==n+1) nxt[i][j]=n+1;
else nxt[i][j]=nxt[nxt[i][j-1]][j-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D)
{
A++,B++,C++,D++;
if(C==D)
{
if(l[C]>=B) return -1;
ll x=get(max(1ll*A,l[C]+1),B).se;
ll ans=0;
for(int i=17;i>=0;i--)
{
ll cc=par[x][i];
if(a[cc]<=a[C]) x=cc,ans+=1<<i;
}
return ans+d[x]-d[C];
}
else
{
ll y=get(C,D).se;
if(l[y]>=B) return -1;
ll x=get(max(1ll*A,l[y]+1),B).se;
ll ans=0;
for(int i=17;i>=0;i--)
{
ll cc=par[x][i];
if(r[cc]<C) x=cc,ans+=1<<i;
}
ll res=inf;
if(r[par[x][0]]>=C&&r[par[x][0]]<=D)
{
res=min(res,ans+2);
x=par[x][0];
}
for(int i=17;i>=0;i--)
{
if(nxt[x][i]<C)
{
x=nxt[x][i];
ans+=1<<i;
}
}
res=min(res,ans+1);
if(r[x]<=D) return res;
else return -1;
}
}
/*int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
//init(7, {3, 2, 1, 6, 4, 5, 7});
//cout << minimum_jumps(4, 4, 6, 6)<<' '<<minimum_jumps(1, 3, 6, 6)<<' '<<minimum_jumps(0, 1, 2, 2);
}*/
