#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7, LG=20;
int T[LIM], lewo[LIM][LG], prawo[LIM][LG], ile[LIM][LG], ma[LIM][LG], n;
void init(int N, vector<int>H) {
n=N;
rep(i, n) T[i+1]=H[i];
stack<pair<int,int>>S;
T[0]=T[n+1]=INF;
rep(i, n+2) {
while(!S.empty() && S.top().st<T[i]) S.pop();
if(!S.empty()) lewo[i][0]=S.top().nd;
else lewo[i][0]=i;
S.push({T[i], i});
}
while(!S.empty()) S.pop();
for(int i=n+1; i>=0; --i) {
while(!S.empty() && S.top().st<T[i]) S.pop();
if(!S.empty()) prawo[i][0]=S.top().nd;
else prawo[i][0]=i;
S.push({T[i], i});
}
for(int j=1; j<LG; ++j) rep(i, n+2) {
lewo[i][j]=lewo[lewo[i][j-1]][j-1];
prawo[i][j]=prawo[prawo[i][j-1]][j-1];
}
rep(i, n+2) {
int p=i;
ile[i][0]=-1;
for(int j=LG-1; j>=0; --j) if(prawo[p][j]<prawo[lewo[i][0]][0]) {
p=prawo[p][j];
ile[i][0]+=1<<j;
}
if(ile[i][0]>0) ma[i][0]=ile[i][0];
}
for(int j=1; j<LG; ++j) rep(i, n+2) {
ile[i][j]=ile[i][j-1]+ile[lewo[i][j-1]][j-1];
ma[i][j]=max(ma[i][j-1], ile[i][j-1]+ma[lewo[i][j-1]][j-1]);
}
}
int minimum_jumps(int a, int b, int l, int r) {
++a; ++b; ++l; ++r;
int p=b;
for(int i=LG-1; i>=0; --i) if(prawo[p][i]<=r) p=prawo[p][i];
if(p<l) return -1;
int x=b;
for(int i=LG-1; i>=0; --i) if(T[lewo[x][i]]<T[p] && lewo[x][i]>=a) x=lewo[x][i];
int sum=1, y=x;
for(int i=LG-1; i>=0; --i) if(prawo[y][i]<l) {
y=prawo[y][i];
sum+=1<<i;
}
int z=T[y], ans=0, akt=0, ans2=0;
y=prawo[y][0];
p=x;
for(int i=LG-1; i>=0; --i) if(T[lewo[x][i]]<T[y]) {
ans=max(ans, akt+ma[x][i]);
akt+=ile[x][i];
x=lewo[x][i];
}
ans=sum-ans;
for(int i=LG-1; i>=0; --i) if(T[lewo[p][i]]<z) {
p=lewo[p][i];
ans2+=1<<i;
}
p=lewo[p][0];
if(prawo[p][0]<=r) ans=min(ans, ans2+2);
return ans;
}
