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