#include "jumps.h"
#include <vector>
#include <stack>
using namespace std;
const int INF = 1e9;
int n;
vector<int> prv, nxt;
int solve(int i, vector<int> &dp);
void init(int N, vector<int> h) {
n = N;
prv.resize(n), nxt.resize(n);
stack<int> s;
for (int i = 0; i < n; i++) {
while (not s.empty() and h[s.top()] <= h[i]) s.pop();
prv[i] = (s.empty() ? -1 : s.top());
s.push(i);
}
while (not s.empty()) s.pop();
for (int i = n - 1; i >= 0; i--) {
while (not s.empty() and h[s.top()] <= h[i]) s.pop();
nxt[i] = (s.empty() ? -1 : s.top());
s.push(i);
}
}
int minimum_jumps(int a, int b, int c, int d) {
vector<int> dp(n, -1);
for (int i = c; i <= d; i++) {
dp[i] = 0;
}
int ans = INF;
for (int i = a; i <= b; i++) {
ans = min(ans, solve(i, dp));
}
return (ans == INF ? -1 : ans);
}
int solve(int i, vector<int> &dp) {
if (i == -1) return INF;
if (dp[i] != -1) return dp[i];
dp[i] = min(1 + solve(prv[i], dp), 1 + solve(nxt[i], dp));
return dp[i];
}
