#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;
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+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));
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];
}
}
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(ind[mn[C].first]>=A) return -1;
ll cur=h[A];
ll ans=0;
for (int j=19;j>=0;j--)
{
if(nqqz[cur][j]!=inf)
{
cur=nqqz[cur][j];
ans+=1LL<<j;
}
}
return limn[cur]-limn[h[C]]+ans;
}
