#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int MxN = 2e5 + 5;
int n, l[MxN], r[MxN];
vector<int> h;
bool sub1 = 1;
void init(int N, std::vector<int> H) {
n = N; h = H;
stack<int> st;
for (int i = 0; i < n; i++) if (h[i] != i + 1) sub1 = 0;
for (int i = 0; i < n; i++) {
l[i] = -1;
while (!st.empty() && h[i] > h[st.top()]) st.pop();
if (!st.empty()) l[i] = st.top();
st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
r[i] = -1;
while (!st.empty() && h[i] > h[st.top()]) st.pop();
if (!st.empty()) r[i] = st.top();
st.emplace(i);
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (sub1) return C - B;
vector<vector<int>> dp(2, vector<int>(n + 5, 1e9));
for (int i = A; i <= B; i++) dp[0][i] = 0;
int ans = 1e9;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n; j++) dp[i & 1][j] = 1e9;
for (int j = 0; j < n; j++) {
if (~l[j]) dp[i & 1][l[j]] = min(dp[i & 1][l[j]], dp[!(i & 1)][j] + 1);
if (~r[j]) dp[i & 1][r[j]] = min(dp[i & 1][r[j]], dp[!(i & 1)][j] + 1);
}
for (int j = C; j <= D; j++) ans = min(ans, dp[i & 1][j]);
if (ans != 1e9) return ans;
}
return (ans == 1e9 ? -1 : ans);
}
