#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> H;
int unde[200005];
const int INF = 1e9;
int tole[200005],tori[200005],parent[200005];
int anc[200005][18],ancri[200005][18];
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);
if(tole[i]>-1 && H[tole[i]] > H[tori[i]])
parent[i] = tole[i];
else
parent[i] = tori[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]++;
}
tori[N]=N;
for(int i=0;i<N;i++)
{
anc[i][0] = parent[i];
ancri[i][0] = tori[i];
}
anc[N][0]=ancri[N][0]=N;
for(int p=1;p<18;p++)
{
for(int i=0;i<=N;i++)
{
anc[i][p] = anc[anc[i][p-1]][p-1];
ancri[i][p] = ancri[ancri[i][p-1]][p-1];
}
}
}
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);
for(int p=17;p>=0;p--)
{
if(tori[anc[cur][p]] < le && tole[cur]!=-1 && H[tole[cur]]<=mxm)
{
cur = anc[cur][p];
pasi += (1<<p);
}
}
while(1)
{
if(tole[cur]==-1 || H[tole[cur]] > mxm)
break;
if(tori[cur]>=le && tori[cur]<=ri)
return pasi+1;
cur = parent[cur];
pasi++;
}
///acum putem merge doar spre dreapta
for(int p=17;p>=0;p--)
{
if(ancri[cur][p] < le)
{
cur = ancri[cur][p];
pasi += (1<<p);
}
}
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);
}
