#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>st;
for(int i=0; i<N; ++i) {
lef[i][0] = rit[i][0] = hi[i][0] = i;
}
for(int i=0; i<N; ++i) {
while(!st.empty() && H[st.top()]<a[i]) {
rit[st.top()][0] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=N-1; i>=0; --i) {
while(!st.empty() && H[st.top()]<a[i]) {
lef[st.top()][0] = i;
st.pop();
}
st.push(i);
}
for(int i=0; i<N; ++i) {
hi[i][0] = (H[lef[i][0]]>H[rit[i][0]]) ? lef[i][0] : rit[i][0];
}
for(int j=1; j<h_max; ++j) {
for(int i=0; i<N; ++i) {
lef[i][j] = lef[lef[i][j-1]][j-1];
rit[i][j] = rit[rit[i][j-1]][j-1];
hi[i][j] = hi[hi[i][j-1]][j-1];
}
}
}
*/
void init(int N, vector<int> H)
{
n=N;
a=H;
stack<int> stk;
for(int i=0;i<n;i++)lef[i][0]=rit[i][0]=hi[i][0]=i;
/*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=0; i<N; ++i) {
while(!stk.empty() && H[stk.top()]<a[i]) {
rit[stk.top()][0] = i;
stk.pop();
}
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i=N-1; i>=0; --i) {
while(!stk.empty() && H[stk.top()]<a[i]) {
lef[stk.top()][0] = i;
stk.pop();
}
stk.push(i);
}
for(int i=0; i<N; ++i) {
hi[i][0] = (H[lef[i][0]]>H[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 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 find_st(int A, int B, int mx) {
int cur = B;
for(int j=h_max-1; j>=0; --j) {
if(lef[cur][j]>=A && a[lef[cur][j]]<mx) {
cur = lef[cur][j];
}
}
return cur;
}
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(rit[hi[cur][i]][0]>=C)continue;
cur=hi[cur][i];
ans+=1<<i;
}
int add=find_dis(cur,C,D);
if(a[hi[cur][0]]<=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;
}
