#include "jumps.h"
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=200100;
const int mxM=104;
const int mxK=50000;
const int MOD=1000000007;
const ll INF=100000000000001;
int N;
int H[mxN];
stack <pii> stk;
int L[mxN], R[mxN];
void make_link()
{
for(int i=0;i<N;i++)
{
while(!stk.empty())
{
pii now=stk.top();
if(now.sec<H[i]) stk.pop();
else break;
}
if(!stk.empty()) L[i]=stk.top().fir;
else L[i]=i;
stk.push({i, H[i]});
}
while(!stk.empty()) stk.pop();
for(int i=N-1;i>=0;i--)
{
while(!stk.empty())
{
pii now=stk.top();
if(now.sec<H[i]) stk.pop();
else break;
}
if(!stk.empty()) R[i]=stk.top().fir;
else R[i]=i;
stk.push({i, H[i]});
}
}
int spL[mxN][20], spR[mxN][20];
int spI[mxN][20];
void make_sparse()
{
for(int i=0;i<N;i++)
{
spL[i][0]=L[i], spR[i][0]=R[i];
}
for(int i=1;i<20;i++)
{
for(int j=0;j<N;j++)
{
spL[j][i]=spL[spL[j][i-1]][i-1];
spR[j][i]=spR[spR[j][i-1]][i-1];
}
}
for(int i=0;i<N;i++) spI[i][0]=(H[L[i]]<H[R[i]] ? R[i] : L[i]);
for(int i=1;i<20;i++)
{
for(int j=0;j<N;j++)
{
spI[j][i]=spI[spI[j][i-1]][i-1];
}
}
}
int seg[4*mxN];
void init_seg(int idx, int s, int e)
{
if(s==e)
{
seg[idx]=H[s]; return;
}
int mid=(s+e)/2;
init_seg(2*idx, s, mid);
init_seg(2*idx+1, mid+1, e);
seg[idx]=max(seg[2*idx], seg[2*idx+1]);
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2) return seg[idx];
int mid=(s1+e1)/2;
return max(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
}
void init(int n, std::vector<int> h) {
N=n;
for(int i=0;i<N;i++) H[i]=h[i];
make_link();
make_sparse();
init_seg(1, 0, N-1);
}
int minimum_jumps(int A, int B, int C, int D)
{
int cnt=0;
if(solv(1, 0, N-1, B, C-1)>solv(1, 0, N-1, C, D)) return -1;
if(B==C-1) return 1;
int minH, maxH;
maxH=solv(1, 0, N-1, C, D);
minH=solv(1, 0, N-1, B+1, C-1);
int ABnow=B;
for(int i=19;i>=0;i--)
{
if(H[spL[ABnow][i]]<maxH && spL[ABnow][i]>=A) ABnow=spL[ABnow][i];
}
if(H[ABnow]>minH) return 1;
for(int i=19;i>=0;i--)
{
if(H[spI[ABnow][i]]<minH)
{
ABnow=spI[ABnow][i];
cnt+=(1<<i);
}
}
if(R[ABnow]>=C) return cnt+1;
if(H[L[ABnow]]>minH && H[L[ABnow]]<maxH) return cnt+2;
for(int i=19;i>=0;i--)
{
if(spR[ABnow][i]<C)
{
ABnow=spR[ABnow][i];
cnt+=(1<<i);
}
}
return cnt+1;
}
