#include "jumps.h"
#include <vector>
#include <set>
#include <cmath>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int const N=2e5+10,LG=20;
int mx[N][LG]={};
int nextmx[N]={},premx[N]={};
bool uni=0;
vector<int>nei[N]={};
int dis[N]={};
int n;
void init(int N,vector<int> H)
{
n=N;
uni=is_sorted(begin(H),end(H));
deque<int>d;
for (int i=0;i<N;i++)
{
nextmx[i]=-1;
if (d.empty())
{
d.push_front(i);
continue;
}
while (d.size()&&H[d.front()]<H[i])
{
nextmx[d.front()]=i;
d.pop_front();
}
d.push_front(i);
}
d={};
for (int i=N-1;i>=0;i--)
{
premx[i]=-1;
if (d.empty())
{
d.push_front(i);
continue;
}
while (d.size()&&H[d.front()]<H[i])
{
premx[d.front()]=i;
d.pop_front();
}
d.push_front(i);
}
for (int i=0;i<N;i++)
{
if (premx[i]!=-1)
nei[i].push_back(premx[i]);
if (nextmx[i]!=-1)
nei[i].push_back(nextmx[i]);
}
}
int minimum_jumps(int A, int B, int C, int D)
{
if (uni)
return C-B;
set<pair<int,int>>s;
for (int i=0;i<n;i++)
{
dis[i]=1e9+10;
if (i>=A&&i<=B)
{
s.insert({0,i});
dis[i]=0;
}
}
while (s.size())
{
int st=(*begin(s)).second;
if (st>=C&&st<=D)
return (*begin(s)).first;
s.erase(*begin(s));
for (auto i:nei[st])
{
if (dis[i]>dis[st]+1)
{
dis[i]=dis[st]+1;
s.insert({dis[i],i});
}
}
}
return -1;
}
