#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <assert.h>
#include <random>
#include <climits>
#include <numeric>
#include <queue>
#include <array>
#define rep(i,s,e) for(int i=(s); i<=(e); i++)
#define ll long long
#define db double
//#define int ll
#define i128 __int128_t
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pll>
#define ub(x) upper_bound((x))
#define lb(x) lower_bound((x))
#define bg begin()
#define ed end()
#define arr2 array<int,2>
#define arr3 array<int,3>
using namespace std;
const int LM=200100;
int N;
int rp[20][LM], p[20][LM], H[LM];
int seg[LM*4];
void seginit(int s=0, int e=N+1, int nd=1){
if(s==e){
seg[nd]=s;
return;
}
int m=s+e>>1;
seginit(s,m,nd*2); seginit(m+1,e,nd*2+1);
seg[nd] = H[seg[nd*2]] > H[seg[nd*2+1]] ? seg[nd*2] : seg[nd*2+1];
}
int Max(int l, int r, int s=0, int e=N+1, int nd=1){
if(e<l || r<s) return N+2;
if(l<=s && e<=r) return seg[nd];
int m=s+e>>1;
int L=Max(l,r, s,m,nd*2), R=Max(l,r, m+1,e,nd*2+1);
return H[L] > H[R] ? L : R;
}
int MaxR(int l, int r, int v){
/*int ret=r;
for(int i=r; i>l; i--){
if(H[i] >= v) return ret;
if(H[ret] < H[i]) ret=i;
}*/
int low=l, hig=r;
while(low<hig){
int mid=low+hig>>1;
if(H[Max(mid,r)] < v) hig=mid;
else low=mid+1;
}
return Max(low,r);
}
int MaxL(int l, int r, int v){
//for(int i=l; i<=r; i++) if(H[i]>v) return i;
int low=l, hig=r;
while(low<hig){
int mid=low+hig>>1;
if(H[Max(l,mid)] > v) hig=mid;
else low=mid+1;
}
return Max(l,low);
}
void init(int N_, vi H_){
N=N_;
rep(i,1,N) H[i]=H_[i-1];
H[0]=N+1; H[N+1]=N+1;
seginit();
vi stk={0};
rep(i,1,N+1){
while(H[stk.back()] < H[i]){
rp[0][stk.back()]=i;
stk.pop_back();
}
p[0][i] = stk.back();
stk.push_back(i);
}
rep(i,1,N){
p[0][i] = H[p[0][i]] > H[rp[0][i]] ? p[0][i] : rp[0][i];
}
rep(i,1,19){
rep(j,1,N){
p[i][j] = p[i-1][p[i-1][j]];
rp[i][j]=rp[i-1][rp[i-1][j]];
}
}
}
int minimum_jumps(int A, int B, int C, int D){
A++;B++;C++;D++;
int ans=1;
int e=Max(C,D);
if(H[Max(B,C-1)] > H[e]) return -1;
int x=MaxR(A,B,H[e]);
e=MaxL(C,D,H[x]);
//cout<<x<<" "<<e<<"\n";
int ANS=1e9, X=x;
rep(E,C,D){
int x=X, e=E;
int ans=1;
for(int i=19; i>=0; i--){
if(H[p[i][x]] < H[e]){
ans += 1<<i; x=p[i][x];
}
}
for(int i=19; i>=0; i--){
if(H[rp[i][x]] < H[e]){
ans += 1<<i; x=rp[i][x];
}
}
if(rp[0][x]==e) ANS = min(ans, ANS);
}
return ANS;
}
