#include "jumps.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 2005;
const int INF_VAL = 1e9;
int dist_matrix[MAXN][MAXN];
int n;
void init(int N, vector<int> H) {
n = N;
vector<vector<int>> gp(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; j++) dist_matrix[i][j] = INF_VAL;
for (int j = i + 1; j < N; ++j) {
if (H[j] > H[i]) {
gp[i].push_back(j);
break;
}
}
for (int j = i - 1; j >= 0; --j) {
if (H[j] > H[i]) {
gp[i].push_back(j);
break;
}
}
}
for (int i = 0; i < N; ++i) {
dist_matrix[i][i] = 0;
queue<int> q;
q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : gp[u]) {
if (dist_matrix[i][v] == INF_VAL) {
dist_matrix[i][v] = dist_matrix[i][u] + 1;
q.push(v);
}
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(n > 2000)return C - B;
int min_ans = INF_VAL;
for (int i = A; i <= B; ++i) {
for (int j = C; j <= D; ++j) {
if (dist_matrix[i][j] < min_ans) {
min_ans = dist_matrix[i][j];
}
}
}
return (min_ans >= INF_VAL) ? -1 : min_ans;
}
