#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 getdist(int cur, int le, int ri)
{
int pasi=0,mxm=0;
for(int i=le;i<=ri;i++)
mxm = max(mxm, H[i]);
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)
{
int mnm=INF;
for(int i=A;i<=B;i++)
mnm = min(mnm, getdist(i,C,D));
if(mnm==INF)
return -1;
else
return mnm;
}
