#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 1000000
vector<vector<int>> edges;
vector<int> H;
int N;
void init(int iN, std::vector<int> iH) {
return;
N = iN;
H = iH;
// create DAG using monotic array
stack<int> st;
edges.resize(N+1);
// create front
for(int i = 0;i < N;i++){
while(!st.empty() && st.top() < H[i]){
st.pop();
}
if(!st.empty()){
edges[H[i]].push_back(st.top());
}
st.push(H[i]);
}
while(!st.empty()) st.pop();
// from back
for(int i = N-1;i >= 0;i--){
while(!st.empty() && st.top() < H[i]){
st.pop();
}
if(!st.empty()){
edges[H[i]].push_back(st.top());
}
st.push(H[i]);
}
}
int minimum_jumps(int A, int B, int C, int D) {
return C-B;
vector<int> dist(N+1,inf);
queue<int> q;
for(int i = A;i <= B;i++){
dist[H[i]] = 0;
q.push(H[i]);
}
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto nxt:edges[cur]){
if(dist[nxt] == inf){
dist[nxt] = dist[cur]+1;
q.push(nxt);
}
}
}
int ans = inf;
for(int i = C;i <= D;i++){
ans = min(ans,dist[H[i]]);
}
if(ans == inf){
return -1;
}
return ans;
}
