#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> H;
const int INF = 1e9;
int parent[200005];
int tole[200005],tori[200005];
void init(int N, std::vector<int> copH)
{
H=copH;
deque<int> dq;
for(int i=0;i<=N;i++)
{
while(!dq.empty() && H[dq.back()] < H[i])
dq.pop_back();
if(dq.empty())
tole[i]=-1;
else
tole[i]=dq.back();
dq.push_back(i);
}
dq.clear();
for(int i=N-1;i>=0;i--)
{
while(!dq.empty() && H[dq.back()] < H[i])
dq.pop_back();
if(dq.empty())
tori[i]=N;
else
tori[i]=dq.back();
dq.push_back(i);
}
}
int getmax(int le, int ri)
{
int mxm=0;
for(int i=le;i<=ri;i++)
mxm = max(mxm, H[i]);
return mxm;
}
int getdist(int cur, int le, int ri)
{
int pasi=0,mxm=getmax(le,ri);
while(1)
{
if(tori[cur]>ri || H[cur] > mxm)
return INF;
if(tori[cur]>=le && tori[cur]<=ri)
return pasi+1;
if(H[tole[cur]] > H[tori[cur]] && H[tole[cur]] < mxm)
{
cur = tole[cur];
}
else
{
cur = tori[cur];
}
pasi++;
}
return pasi;
}
int minimum_jumps(int A, int B, int C, int D)
{
if(getmax(B+1,C-1) > getmax(C,D))
return -1;
if(H[B] > getmax(C,D))
return -1;
int primu=-1;
for(int i=A;i<=B;i++)
{
if(getmax(i,B)==H[i] && H[i] < getmax(C,D))
{
primu=i;
break;
}
}
if(primu==-1)
return -1;
else
return getdist(primu,C,D);
}
