#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
const int MAX_N = 2e5 + 5;
const int INF = 1e9 + 7;
int N;
bool subtask1;
int H[MAX_N], L[MAX_N], R[MAX_N], dp[MAX_N];
vector <pair <int, int>> trees;
void init(int n, vector <int> h) {
N = n;
subtask1 = true;
for(int i = 1; i <= N; i++) {
H[i] = h[i - 1];
trees.emplace_back(H[i], i);
if(H[i] < H[i - 1]) {
subtask1 = false;
}
}
sort(trees.rbegin(), trees.rend());
stack <int> stk;
for(int i = 1; i <= N; i++) {
while(!stk.empty() and H[stk.top()] < H[i]) {
stk.pop();
}
L[i] = -1;
if(!stk.empty()) {
L[i] = stk.top();
}
stk.push(i);
}
while(!stk.empty()) {
stk.pop();
}
for(int i = N; i >= 1; i--) {
while(!stk.empty() and H[stk.top()] < H[i]) {
stk.pop();
}
R[i] = -1;
if(!stk.empty()) {
R[i] = stk.top();
}
stk.push(i);
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
if(subtask1 == true) {
return C - B;
}
int ans = INF;
for(int i = 1; i <= N; i++) {
dp[i] = INF;
}
for(auto [h, i] : trees) {
if(C <= i and i <= D) {
dp[i] = 0;
}
if(L[i] != -1) {
dp[i] = min(dp[i], dp[L[i]] + 1);
}
if(R[i] != -1) {
dp[i] = min(dp[i], dp[R[i]] + 1);
}
if(A <= i and i <= B) {
ans = min(ans, dp[i]);
}
}
if(ans == INF) {
return -1;
}
return ans;
}
