#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int nx=2e5+5, kx=18; int l[nx], r[nx], n; vector<int> d[nx]; void init(int N, std::vector<int> H) { n=N; stack<int> s; for (int i=0; i<N; i++) l[i]=r[i]=N; for (int i=0; i<N; i++) { while (!s.empty()&&H[s.top()]<H[i]) s.pop(); if (!s.empty()) l[i]=s.top(), d[s.top()].push_back(i); s.push(i); } while (!s.empty()) s.pop(); for (int i=N-1; i>=0; i--) { while (!s.empty()&&H[s.top()]<H[i]) s.pop(); if (!s.empty()) r[i]=s.top(), d[s.top()].push_back(i); s.push(i); } } int minimum_jumps(int A, int B, int C, int D) { vector<int> mn(n, 1e9); queue<int> q; for (int i=C; i<=D; i++) mn[i]=0, q.push(i); while (!q.empty()) { auto u=q.front(); q.pop(); for (auto v:d[u]) if (mn[v]>mn[u]+1) q.push(v), mn[v]=mn[u]+1; } int res=1e9; for (int i=A; i<=B; i++) res=min(res, mn[i]); if (res==1e9) return -1; return res; }