#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];
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]=0;
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+1;
else R[i]=st.top();
st.push(i);
}
for(int i=1;i<=n;i++) sp[i][0]=A[i];
for(int j=1;(1<<j)<=n;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]);
}
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) return -1;
int pl=a,pr=b,ans=0;
while(pr<c)
{
int p=pos[rmq(pl,pr)];
pl=max(l,L[p]),pr=min(r,R[p]),ans++;
}
return ans;
}
