#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> H;
vector<int> sorted;
vector< vector<int> > adj;
void init(int n, vector<int> h)
{
N = n;
H = h;
adj.resize( N );
vector<int> ind(N+1);
{
stack<int> closest;
for(int i = 0; i < N; ++i)
{
ind[H[i]] = i;
while(!closest.empty() && closest.top() < H[i])
closest.pop();
if( !closest.empty() )
{
adj[i].push_back( ind[closest.top()] );
}
closest.push( H[i] );
}
}
stack<int> closest;
for(int i = N-1; i >= 0; --i)
{
while(!closest.empty() && closest.top() < H[i])
closest.pop();
if( !closest.empty() )
{
adj[i].push_back( ind[closest.top()] );
}
closest.push( H[i] );
}
}
int minimum_jumps(int A, int B, int C, int D)
{
int minJ = N+1;
queue<int> q;
vector<int> distance(N, N+1);
for(int i = A; i <= B; ++i)
{
q.push(i);
distance[i] = 0;
}
while(!q.empty())
{
int u = q.front();
q.pop();
if( C <= u && u <= D)
minJ = min(minJ, distance[u]);
for(const int& v : adj[u])
{
if(distance[v] <= distance[u] + 1)
continue;
distance[v] = distance[u] + 1;
q.push(v);
}
}
if(minJ == N+1)
minJ = -1;
return minJ;
}
