#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)(1e15)
#define dbg(x) cerr <<#x << ' ' << x <<endl;
using namespace std;
ll n;
vector<ll> h;
vector<pair<ll,ll>> mn;
vector<ll> ind;
vector<ll> limn;
vector<vector<ll>> nqqz;
vector<vector<ll>> nqqz2;
ll maxn=2e5;
vector<ll> tree(4*maxn+3);
void update(ll node, ll l, ll r, ll pos, ll val)
{
if(pos < l || pos > r)return;
if(l==r)
{
tree[node]=val;
return;
}
ll mid=(l+r)/2;
update(node*2+1,l,mid,pos,val);
update(node*2+2,mid+1,r,pos,val);
tree[node]=max(tree[node*2+1],tree[node*2+2]);
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
if(max(l,x) > min(r,y))return 0;
if(x<=l && r<=y)return tree[node];
ll mid=(l+r)/2;
return max(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y));
}
void init(int N, std::vector<int> H)
{
n=N;
for (int i=0;i<n;i++) h.push_back(H[i]);
mn.resize(n+1);
stack<ll> s;
for (int i=0;i<n;i++)
{
while(s.size() && (s.top() < h[i]))
{
s.pop();
}
if(s.size())
{
mn[h[i]].first=s.top();
}
s.push(h[i]);
}
while(s.size())s.pop();
for (int i=n-1;i>=0;i--)
{
while(s.size() && (s.top() < h[i]))
{
s.pop();
}
if(s.size())
{
mn[h[i]].second=s.top();
}
s.push(h[i]);
}
ind.resize(n+1);
for (int i=0;i<n;i++)
{
ind[h[i]]=i;
update(0,0,n-1,i,h[i]);
}
limn.resize(n+1);
for (int i=n-1;i>=0;i--)
{
if(mn[h[i]].second!=0)
{
limn[h[i]]=1+limn[mn[h[i]].second];
}
}
nqqz.assign(n+1,vector<ll>(20,inf));
nqqz2.assign(n+1,vector<ll>(20,inf));
for (int i=n;i>=1;i--)
{
for (int j=0;j<20;j++)
{
if(j==0)
{
if(max(mn[i].first,mn[i].second)!=0)
{
nqqz[i][j]=max(mn[i].first,mn[i].second);
}
}
else
{
if(max(mn[i].first,mn[i].second)!=0)
{
ll x=nqqz[i][j-1];
if(x!=inf)
{
nqqz[i][j]=nqqz[x][j-1];
}
}
}
}
}
// tnqiza 2:
for (int i=n;i>=1;i--)
{
for (int j=0;j<20;j++)
{
if(j==0)
{
if(mn[i].second!=0)
{
nqqz2[i][j]=mn[i].second;
}
}
else
{
if(mn[i].second!=0)
{
ll x=nqqz2[i][j-1];
if(x!=inf)
{
nqqz2[i][j]=nqqz2[x][j-1];
}
}
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
ll kbir=query(0,0,n-1,C,D);
if(mn[kbir].first!=0 && ind[mn[kbir].first] >= B) return -1;
ll awal;
if(mn[h[C]].first==0 || ind[mn[h[C]].first] < B) awal=h[C];
else awal=mn[h[C]].second;
ll indd=A;
if(mn[kbir].first!=0)
{
indd=max(ind[mn[kbir].first]+1,(ll)A);
}
ll cur=query(0,0,n-1,indd,B);
if(cur > awal) return 1;
ll ans=0;
for (int j=19;j>=0;j--)
{
if(nqqz[cur][j]!=inf && nqqz[cur][j]<awal)
{
cur=nqqz[cur][j];
ans+=1LL<<j;
}
}
if(mn[cur].second==awal) return ans+1;
if(mn[cur].first < kbir) return ans+2;
return ans + limn[cur]-limn[awal];
}
