#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
int const n_max=2e5+10;
int const h_max=18;
int rit[n_max][h_max],lef[n_max][h_max],hi[n_max][h_max];
int n;
vector<int> a;
void init(int N, vector<int> H)
{
n=N;
a=H;
stack<int> stk;
for(int i=0;i<n;i++)
{
while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
if(stk.empty()) lef[i][0]=i;
else lef[i][0]=stk.top();
stk.push(i);
}
while(!stk.empty())stk.pop();
for(int i=n-1;i>=0;i--)
{
while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
if(stk.empty()) rit[i][0]=i;
else rit[i][0]=stk.top();
stk.push(i);
}
for(int i=0;i<n;i++)
{
hi[i][0]=(a[lef[i][0]]>a[rit[i][0]])? lef[i][0]:rit[i][0];
}
for(int i=1;i<h_max;i++)
{
for(int j=0;j<n;j++)
{
lef[j][i]=lef[rit[j][i-1]][i-1];
rit[j][i]=rit[rit[j][i-1]][i-1];
hi[j][i]=hi[hi[j][i-1]][i-1];
}
}
}
int find_mx(int C,int D)
{
int cur=C;
for(int i=h_max-1;i>=0;i--)
{
if(rit[cur][i]<=D) cur=rit[cur][i];
}
return a[cur];
}
int find_st(int A,int B,int mx)
{
int cur=A;
for(int i=h_max-1;i>=0;i--)
{
if(rit[cur][i]<=B&&a[rit[cur][i]]<mx) cur=rit[cur][i];
}
return a[cur];
}
int find_dis(int cur,int C,int D)
{
int ret=0;
for(int i=h_max-1;i>=0;i--)
{
if(rit[cur][i]>=C)continue;
cur=rit[cur][i];
ret+=1<<i;
}
ret++;
cur=rit[cur][0];
if(C<=cur&&cur<=D)return ret;
return -1;
}
int minimum_jumps(int A, int B, int C, int D)
{
int mx=find_mx(C,D);
int st=find_st(A,B,mx);
if(a[st]>mx)return -1;
int ans=0;
int cur=st;
for(int i=h_max-1;i>=0;i--)
{
if(a[hi[cur][i]]>=mx)continue;
if(hi[cur][i]>=C)continue;
cur=hi[cur][i];
ans+=1<<i;
}
int add=find_dis(cur,C,D);
if(a[cur]<mx)
{
int nadd=find_dis(hi[cur][0],C,D);
if(nadd!=-1)add=min(add,nadd+1);
}
if(add==-1)return -1;
return ans+add;
}
