#include "jumps.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<int> h;
vector<int> lm;
vector<int> rm;
int n;
void init(int N, std::vector<int> H) {
h=H;
n=N;
vector<pair<int,int>> stck;
lm.clear(),rm.clear();
REP(i,0,N){
while(stck.size() && stck.back().fi < H[i])stck.pop_back();
lm.pb(-1);
if(stck.size())lm.back() = (stck.back().se);
stck.pb({h[i],i});
}
stck.clear();
REP(ix,0,N){
auto i=N-1-ix;
while(stck.size() && stck.back().fi < H[i])stck.pop_back();
rm.pb(-1);
if(stck.size())rm.back() = (stck.back().se);
stck.pb({h[i],i});
}
reverse(rm.begin(),rm.end());
}
int minimum_jumps(int A, int B, int C, int D) {
int mx=0;
REP(i,C,D+1)mx=max(h[i],mx);
int b=-1;
int roll=-1;
REP(ix,A,B+1){
auto i=A+B-ix;
roll=max(roll,h[i]);
if(roll>mx)break;
if(roll==h[i])b=i;
}
// cerr<<"SELECT "<<b<<endl;
if(b==-1){return -1;}
roll=b;
REP(i,1,n+1){
// cerr<<b<<": "<<lm[b]<<", "<<rm[b]<<endl;
if(C <= lm[b] && lm[b] <= D)return i;
if(C <= rm[b] && rm[b] <= D)return i;
int lc=-1,rc=-1;
if(lm[b]!=-1 && h[lm[b]] <= mx)lc=h[lm[b]];
if(rm[b]!=-1 && h[rm[b]] <= mx)rc=h[rm[b]];
int prv=b;
if(lc > rc)b=lm[b];
else if(rc > lc)b=rm[b];
else break;
// assert(h[b]>h[prv]);
}
REP(i,A,D+1)if(h[i]>mx)return -1;
assert(0);
}
