#include "jumps.h"
#include <vector>
#include "bits/stdc++.h"
using namespace std;
bool sub1 = true;
const int MAXN = 2e5+5, SMALL = 2e3+5;
vector< vector<int> > adj(MAXN), revadj(MAXN);
vector< vector<int> > dist(SMALL, vector<int>(SMALL, 1e9));
int sparse[SMALL][12][SMALL];
int indeg[MAXN];
int lg[MAXN];
int n;
void init(int N, vector<int> H) {
lg[1] = 0;
for(int i = 2; i < MAXN; i++)
lg[i] = lg[i / 2] + 1;
n = N;
stack<int> curr;
for(int i = 0; i < N; i++)
{
if(H[i] != i + 1)
sub1 = false;
while(!curr.empty() && H[curr.top()] < H[i])
{
int v = curr.top();
curr.pop();
adj[v].push_back(i);
revadj[i].push_back(v);
indeg[i]++;
}
curr.push(i);
}
while(!curr.empty())
{
curr.pop();
}
for(int i = N - 1; i >= 0; i--)
{
while(!curr.empty() && H[curr.top()] < H[i])
{
int v = curr.top();
curr.pop();
adj[v].push_back(i);
revadj[i].push_back(v);
indeg[i]++;
}
curr.push(i);
}
if(N <= 2000) {
for(int i = 0; i < N; i++)
{
queue< int > ord;
vector<bool> visited(N, false);
dist[i][i] = 0;
visited[i] = true;
ord.push(i);
while(!ord.empty())
{
int v = ord.front();
ord.pop();
for(int e : revadj[v])
{
if(visited[e])
continue;
dist[e][i] = dist[v][i] + 1;
visited[e] = true;
ord.push(e);
}
}
}
/*for(int i = 0; i < N; i++)
{
for(int a = 0; a < N; a++)
cout << i << " " << a <<": " << dist[i][a] << "\n";
}*/
for(int i = 0; i < N; i++)
{
for(int a = 0; a < N; a++)
sparse[i][0][a] = dist[i][a];
for(int bit = 1; bit <= 11; bit++)
{
for(int j = 0; j + (1 << bit) - 1 < N; j++) {
sparse[i][bit][j] = min(sparse[i][bit - 1][j], sparse[i][bit - 1][j + (1 << (bit - 1))]);
//cout << i << " " << bit << " " << j << " " << sparse[i][bit][j] << "\n";
}
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(sub1) // Subtask 1
{
return C - B;
}
//Subtask 2, 3
if(n <= 2000) {
int ans = 1e9;
for(int i = A; i <= B; i++)
{
int add = lg[D - C + 1];
ans = min(ans, min(sparse[i][add][C], sparse[i][add][D - (1 << add) + 1]));
//cout << i << " " << add << " " << sparse[i][add][C] << " " << sparse[i][add][D - (1 << add) + 1] << "\n";
}
if(ans == 1e9)
ans = -1;
return ans;
}
//Subtask 4
vector<bool> visited(n, false);
vector<int> dist(n, 1e9);
queue<int> curr;
for(int i = C; i <= D; i++)
{
dist[i] = 0;
curr.push(i);
visited[i] = true;
}
while(!curr.empty())
{
int v = curr.front();
curr.pop();
for(int e : revadj[v])
{
if(visited[e])
continue;
visited[e] = true;
dist[e] = dist[v] + 1;
curr.push(e);
}
}
int ans = 1e9;
for(int i = A; i <= B; i++)
ans = min(ans, dist[i]);
if(ans == 1e9)
ans = -1;
return ans;
}
