#include"jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int L[MAXN],R[MAXN],sp[MAXN][20],A[MAXN],pos[MAXN],shiftr[MAXN][20];
pair<int,int> nex[MAXN][20];
int getlog(long long n) { return 63-__builtin_clzll(n); }
int rmq(int l,int r)
{
int lg=getlog(r-l+1);
return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
void init(int n,vector<int> H)
{
for(int i=1;i<=n;i++) A[i]=H[i-1],pos[A[i]]=i;
stack<int> st;
for(int i=1;i<=n;i++)
{
while(!st.empty()&&H[i-1]>H[st.top()-1]) st.pop();
if(st.empty()) L[i]=1;
else L[i]=st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=n;i;i--)
{
while(!st.empty()&&H[i-1]>H[st.top()-1]) st.pop();
if(st.empty()) R[i]=n;
else R[i]=st.top();
st.push(i);
}
for(int i=1;i<=n;i++) sp[i][0]=A[i],nex[i][0]={L[i],R[i]},shiftr[i][0]=R[i];
for(int j=1;j<=17;j++) for(int i=1;i<=n-(1<<j)+1;i++) sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
for(int j=1;j<=17;j++) for(int i=1;i<=n;i++)
{
shiftr[i][j]=shiftr[shiftr[i][j-1]][j-1];
nex[i][j]=nex[pos[rmq(nex[i][j-1].first,nex[i][j-1].second)]][j-1];
}
}
int minimum_jumps(int a,int b,int c,int d)
{
a++,b++,c++,d++;
int mx=rmq(c,d),l=1,r=d;
for(int i=b;i>0;i--) if(A[i]>mx)
{
a=max(a,i+1),l=i+1;
break;
}
if(a>b||(b+1<=c-1&&rmq(b+1,c-1)>mx)) return -1;
int pl=a,pr=b,ans=0;
for(int i=17;i+1;i--)
{
int p=pos[rmq(pl,pr)],u=nex[p][i].first,v=nex[p][i].second;
if(u>=l&&v<c) pl=u,pr=v,ans+=(1<<i);
}
if(R[rmq(pl,pr)]>=c) return ans+1;
pr=R[rmq(pl,pr)],pl=l;
for(int i=17;i+1;i--) if(shiftr[pos[rmq(pl,pr)]][i]<c) pr=shiftr[pos[rmq(pl,pr)]][i],ans+=(1<<i);
return ans+1;
}
