#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 vis[N]={};
vector<vector<int>>ans;
int ind[N]={};
bool uni=0;
void init(int N,vector<int> H)
{
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 (!vis[i])
{
int z=i;
vis[z]=1;
ans.push_back({z});
ind[z]=ans.size()-1;
while (nextmx[z]!=-1&&!vis[nextmx[z]])
{
z=nextmx[z];
vis[z]=1;
ans.back().push_back(z);
ind[z]=ans.size()-1;
}
}
}
}
int minimum_jumps(int A, int B, int C, int D)
{
if (uni)
return C-B;
int minsteps=1e9+10;
for (int i=A;i<=B;i++)
{
int ex=0;
int z=i;
while (z!=-1)
{
if (ex>minsteps)
break;
int cnt=ex++;
int prez=z;
while (ans[ind[z]].back()<C&&z!=-1)
{
cnt+=ans[ind[z]].size()-(lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]));
if (nextmx[ans[ind[z]].back()]==-1)
{
cnt=1e9+10;
break;
}
z=nextmx[ans[ind[z]].back()];
}
if (z==-1||cnt==1e9+10)
{
z=premx[prez];
continue;
}
int f=lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),C)-begin(ans[ind[z]]);
if (ans[ind[z]][f]<=D)
{
int g=lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]);
cnt+=f-g;
minsteps=min(cnt,minsteps);
}
z=premx[prez];
}
}
if (minsteps==1e9+10)
return -1;
return minsteps;
}
