#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;
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;
}
limn.resize(n);
for (int i=n-1;i>=0;i--)
{
if(mn[h[i]].second!=0)
{
limn[h[i]]=1+limn[mn[h[i]].second];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
ll maxe=0;
for (int i=A;i<=C;i++)
{
maxe=max(h[i],maxe);
}
if(maxe!=h[C]) return -1;
ll cur=h[A];
ll l3ibat=0;
ll ans=inf;
while(cur<h[C])
{
ans=min(ans,l3ibat+limn[cur]-limn[h[C]]);
l3ibat++;
if(mn[cur].first==0 && mn[cur].second==0)
{
break;
}
cur=max(mn[cur].first,mn[cur].second);
}
return ans;
}
