#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair <ll, ll>;
int n;
const int N = 2e5 + 5;
const int INF = 1e6;
int nums[N], L[N], R[N];
vector <int> paths[N];
void init(int _n, vector<int> _nums) {
n = _n;
nums[0] = nums[n+1] = INF;
for (int i = 1; i <= n; i++) nums[i] = _nums[i-1];
stack <int> stk;
stk.push(0);
for (int i = 1; i <= n; i++) {
while(nums[stk.top()] < nums[i]) stk.pop();
L[i] = stk.top();
stk.push(i);
}
while(!stk.empty()) stk.pop();
stk.push(n+1);
for (int i = n; i > 0; i--) {
while(nums[stk.top()] < nums[i]) stk.pop();
R[i] = stk.top();
stk.push(i);
}
// for (int i = 1; i <= n; i++) {
// paths[i].pb(L[i]);
// paths[i].pb(R[i]);
// cout << i << ": " << nums[L[i]] << ' ' << nums[i] << ' ' << nums[R[i]] << '\n';
// }
}
int C, D;
int dp[N];
int solve(int pos) {
int& res = dp[pos];
if (res != -1) return res;
if (pos == 0 || pos == n+1) return INF;
if (C <= pos && pos <= D) return 0;
return res = 1+min(solve(L[pos]), solve(R[pos]));
}
int minimum_jumps(int A, int B, int _C, int _D) {
C = _C+1;
D = _D+1;
int ans = INF;
for (int i = 0; i <= n+1; i++) dp[i] = -1;
for (int i = A+1; i <= B+1; i++) {
ans = min(ans, solve(i));
}
// for (int i = 1; i <= n; i++) {
// cout << solve(i) << " \n"[i==n];
// }
return ans == INF ? -1 : ans;
}
