#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> H;
int unde[200005];
const int INF = 1e9;
int parent[200005];
int tole[200005],tori[200005];
int rmq[200005][18];
int p2[200005];
void init(int N, std::vector<int> copH)
{
H=copH;
deque<int> dq;
for(int i=0;i<N;i++)
{
unde[H[i]]=i;
rmq[i][0]=H[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);
}
for(int p=1;p<18;p++)
for(int i=0;i+(1<<p)-1<N;i++)
rmq[i][p] = max(rmq[i][p-1], rmq[i+(1<<(p-1))][p-1]);
for(int i=1;i<=N;i++)
{
p2[i]=p2[i-1];
while((1<<(p2[i]+1))<=i)
p2[i]++;
}
}
int getmax(int le, int ri)
{
if(le>ri)
return 0;
int p = p2[ri-le+1];
return max(rmq[le][p], rmq[ri-(1<<p)+1][p]);
}
int getdist(int cur, int le, int ri)
{
int pasi=0,mxm=getmax(le,ri);
while(1)
{
if(H[tole[cur]] > mxm)
break;
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++;
}
///acum putem merge doar spre dreapta
while(cur<le)
{
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 st=A,dr=B,primu=-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(getmax(mij,B) < getmax(C,D))
{
primu=unde[getmax(mij,B)];
dr=mij-1;
}
else
{
st=mij+1;
}
}
if(primu==-1)
return -1;
else
return getdist(primu,C,D);
}
