#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
const int INF = 2e6;
vector<vector<int>> adj(2000);
vector<vector<int>> dist(2000, vector<int>(2000, INF));
int powtwo = (int)pow(2, __lg(2000) + !!(2000 & (2000-1)));
void bfs(int x)
{
queue<int> q;
vector<bool> visited(n);
int start = x;
visited[start] = true;
dist[start][start] = 0;
q.push(start);
while (!q.empty()) {
int s = q.front(); q.pop();
for (auto u : adj[s]) {
if (visited[u]) continue;
visited[u] = true;
dist[start][u] = dist[start][s]+1;
q.push(u);
}
}
}
struct SegmentTree {
vector<int> t;
SegmentTree(int power) : t(2*power) {}
void build(vector<int>& a, int v, int tl, int tr) {
if (tl == tr) {
if (tl < (int)a.size()) t[v] = a[tl];
else t[v] = INF;
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = min(t[v*2], t[v*2+1]);
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return INF;
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
return min(query(v*2, tl, tm, l, min(r, tm)),
query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
};
vector<SegmentTree> segdist;
void init(int N, std::vector<int> H) {
n = N;
for (auto u: H) {h.push_back(u);}
h.shrink_to_fit();
for (int i=0; i<n; i++)
{
for (int j=i; j<n; j++)
{
if (h[i] < h[j]) {adj[i].push_back(j); break;};
}
for (int j=i; j>=0; j--)
{
if (h[i] < h[j]) {adj[i].push_back(j); break;};
}
}
for (int i=0; i<n; i++) {bfs(i);}
for (int i=0; i<n; i++)
{
SegmentTree segtree(powtwo);
segtree.build(dist[i], 1, 0, powtwo-1);
segdist.push_back(segtree);
}
}
int minimum_jumps(int A, int B, int C, int D) {
int answer = INF;
for (int i=A; i<=B; i++)
{
answer = min(answer, segdist[i].query(1, 0, powtwo-1, C, D));
}
return (answer >= INF ? -1 : answer);
}
