#include <bits/stdc++.h>
using namespace std;
int n;
int h[200005];
int l[200005],r[200005];
int Log2[200005];
int rmq[200005][25],u[200005][25],ur[200005][25];
void get_lr()
{
stack<int> st;
for(int i=1; i<=n; i++)
{
while(!st.empty() && h[i] > h[st.top()])
{
st.pop();
}
if(st.empty())
{
l[i] = 0;
}
else
{
l[i] = st.top();
}
st.push(i);
}
while(!st.empty())
{
st.pop();
}
for(int i=n; i>=1; i--)
{
while(!st.empty() && h[i] > h[st.top()])
{
st.pop();
}
if(st.empty())
{
r[i] = 0;
}
else
{
r[i] = st.top();
}
st.push(i);
}
}
void binary_lifting()
{
for(int i=2; i<=n; i++)
{
Log2[i] = 1 + Log2[i/2];
}
for(int i=1; i<=n; i++)
{
rmq[i][0] = h[i];
ur[i][0] = r[i];
if(!l[i])
{
u[i][0] = r[i];
continue;
}
if(!r[i])
{
u[i][0] = l[i];
continue;
}
if(h[l[i]] > h[r[i]])
{
u[i][0] = l[i];
}
else
{
u[i][0] = r[i];
}
}
for(int k=1; k<=Log2[n]+1; k++)
{
for(int i=1; i<=n; i++)
{
u[i][k] = u[u[i][k-1]][k-1];
ur[i][k] = ur[ur[i][k-1]][k-1];
if(i + (1<<k) - 1 <= n)
{
rmq[i][k] = max(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
}
}
}
}
int query_max(int x, int y)
{
int k = Log2[y - x + 1];
return max(rmq[x][k],rmq[y-(1<<k)+1][k]);
}
void init(int N, vector<int> H)
{
n = N;
for(int i=1; i<=n; i++)
{
h[i] = H[i-1];
}
get_lr();
binary_lifting();
}
int get_poz(int a, int b, int c, int d)
{
int st = a;
int dr = b;
int val = 0;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(query_max(mij,b) < query_max(c,d))
{
val = query_max(mij,b);
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
st = a;
dr = b;
int poz = 0;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(query_max(mij,b)>=val)
{
poz = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
return poz;
}
int minimum_jumps(int a, int b, int c, int d)
{
++a,++b,++c,++d;
if(query_max(b,c-1) > query_max(c,d))
{
return -1;
}
int poz = get_poz(a,b,c,d);
int rez = 0;
for(int p=Log2[n]+1; p>=0; p--)
{
if(r[u[poz][p]] && r[u[poz][p]]<c)
{
rez += (1<<p);
poz = u[poz][p];
}
}
if(r[poz]>=c)
{
++rez;
return rez;
}
if(r[l[poz]]<=d)
{
rez += 2;
return rez;
}
for(int p=Log2[n]+1; p>=0; p--)
{
if(ur[poz][p] && ur[poz][p]<c)
{
rez += (1<<p);
poz = ur[poz][p];
}
}
++rez;
poz = r[poz];
return rez;
}
