#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n,k;
const int mxn = 2e5+5;
int s[4*mxn];
vector<int> sol(n,-1),sag(n,-1);
vector<int> sonra,kac;
void yap(int node,int l,int r)
{
if(l==r)
{
s[node] = a[l];
return;
}
int mid = (l+r)/2;
yap(2*node,l,mid);
yap(2*node+1,mid+1,r);
s[node] = max(s[2*node],s[2*node+1]);
}
int bul(int node,int l,int r,int x,int y)
{
if(l>=x && r<=y)return s[node];
if(l>y || r<x) return 0;
int mid = (l+r)/2;
return max(bul(2*node,l,mid,x,y),bul(2*node+1,mid+1,r,x,y));
}
void init(int N, std::vector<int> h)
{
n = N;
a = h;
k = 0;
while(k*k<n)k++;
stack<int> s;
sol.resize(n,-1);
sag.resize(n,-1);
vector<array<int,2>> b(n);
for(int i=0;i<n;i++)
{
b[i] = {a[i],i};
while(s.size() && a[s.top()]<a[i])
{
s.pop();
}
if(s.size()) sol[i] = s.top();
s.push(i);
}
sort(b.begin(),b.end());
while(s.size()) s.pop();
for(int i=n-1;i>=0;i--)
{
while(s.size() && a[s.top()]<a[i]) s.pop();
if(s.size()) sag[i] = s.top();
s.push(i);
}
sonra.resize(n,-1);
kac.resize(n,1e9);
for(int i=n-1;i>=0;i--)
{
int x = b[i][1];
int l = sol[x],r = sag[x];
// cout << x << " "<< l << " "<< r << endl;
if(sol[x]!=-1&& (sag[sol[x]]>sag[x]))
{
kac[x] = kac[sol[x]]+1;
sonra[x] = sonra[sol[x]];
}
if(sag[x]!=-1 && sag[x]/k!=x/k)
{
kac[x] = 1;
sonra[x] = sag[x];
}
if(sag[x]!=-1 && kac[sag[x]]+1<kac[x])
{
kac[x] = kac[sag[x]]+1;
sonra[x] = sonra[sag[x]];
}
//cout << kac[x] << " "<< sonra[x] << endl;
}
yap(1,0,n-1);
}
int minimum_jumps(int A, int x, int y, int D)
{
int mx = bul(1,0,n-1,x,y);
if(mx!=a[y])
return -1;
int ans = 0;
while(sonra[x]!=-1 && sonra[x]/k<=y/k)
{
ans+=kac[x];
x = sonra[x];
// cout << x << endl;
}
while(x!=y)
{
ans++;
//cout << x << endl;
x = sag[x];
}
return ans;
}
