#include "jumps.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
#define ll long long int
#define vi vector<ll>
using namespace std;
const int mxn = 200005;
int v[mxn];
int n;
vi adj[mxn];
const int mxn2 = 2005;
int dist[mxn2][mxn2];
int tree[mxn2][mxn2 * 4];
void upd(int dex, int pos, int num){
pos += n;
tree[dex][pos] = num;
for(pos/=2; pos >= 1; pos/=2){
tree[dex][pos] = min(tree[dex][pos * 2], tree[dex][pos * 2 + 1]);
}
}
int quer(int dex, int l, int r){
l += n; r+=n;
int ret = 1e9;
while(l <= r){
if(l % 2 == 1){
ret = min(ret, tree[dex][l++]);
}
if(r % 2 == 0){
ret = min(ret, tree[dex][r--]);
}
l/=2;
r/=2;
}
return ret;
}
void init(int N, std::vector<int> H) {
n = N;
f0r(i,N)v[i] = H[i];
if(n <= 2000){
f0r(i, n){
for(int j = i-1;j>=0;j--){
if(v[j] > v[i]){
adj[i].pb(j);
break;
}
}
}
f0r(i, n){
for(int j = i+1;j<n;j++){
if(v[j] > v[i]){
adj[i].pb(j);
break;
}
}
}
f0r(i, n)f0r(j,n)dist[i][j] = 1e9;
f0r(i,n){
queue<int>q;
dist[i][i] = 0;
vector<bool>vis(n, false);
vis[i] = 1;
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(vis[u])continue;
q.push(u);
dist[i][u] = min(dist[i][cur] + 1, dist[i][u]);
}
}
}
f0r(i, n){
f0r(j, n){
upd(i, j, dist[i][j]);
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(n > 2000)return C - B;
else{
int ans = 1e9;
for(int i = A; i<=B;i++){
ans = min(ans, quer(i, C, D));
}
if(ans == 1e9)return -1;
else return ans;
}
}
