#include<bits/stdc++.h>
using namespace std;
#include "jumps.h"
//#include "stub.cpp"
#define F first
#define S second
#define double long double
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
namespace{
const int mxn = 2e5 + 5;
int l[mxn],r[mxn];
int n, h[mxn], o[20][mxn], R[20][mxn];
int T[20][mxn];
int chmax(int a,int b){
return (h[a]>h[b]?a:b);
}
int get(int l,int r){
int g=__lg(r-l+1);
return chmax(T[g][l],T[g][r-(1<<g)+1]);
}
}
void init(int N, std::vector<int> H) {
n = N;
h[0] = 2e9, h[n + 1] = 2e9;
for(int i = 1; i <= n; i++){
h[i] = H[i - 1];
}
vector<int>st;
st.pb(0);
for(int i = 1; i <= n ; i++){
while(sz(st) and h[st.back()] < h[i]) st.pop_back();
l[i] = st.back();
st.pb(i);
}
st.clear();
st.pb(n + 1);
R[0][n + 1] = n + 1;
o[0][n + 1] = n + 1;
for(int i = n ; i > 0; i--){
while(sz(st) and h[st.back()] < h[i]) st.pop_back();
r[i] = st.back();
st.pb(i);
}
for(int j=0;j<=n;j++){
o[0][j]=chmax(l[j],r[j]);
R[0][j]=r[j];
T[0][j]=j;
}
for(int i = 1; i < 20; i++){
for(int j = 0; j <= n + 1; j++){
o[i][j] = chmax(o[i-1][o[i-1][j]], o[i-1][o[i-1][j]]);
R[i][j] = R[i-1][R[i-1][j]];
//cout << i << ' ' << j << ' ' << l[i][j] << ' ' << r[i][j] << '\n';
}
}
for(int i=1;i<20;i++){
for(int j=0;j+(1<<i)-1<=n+1;j++){
//cout<<j+(1<<(i-1))<<'\n';
T[i][j]=chmax(T[i-1][j],T[i-1][j+(1<<(i-1))]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
int mx=get(C,D);
int mx2=get(B,C-1);
if(h[mx2]>h[mx]) return -1;
int tl=A,tr=B;
while(tl<tr){
int mid=(tl+tr)/2;
if(h[get(mid,B)]<h[mx]){
tr=mid;
}
else{
tl=mid+1;
}
}
int x=get(tl,B);
int ans = 0;
for(int i = 19; i >= 0; i--){
int y=o[i][x];
//cout << nl << ' ' << nr << '\n';
if(h[y] < h[mx2]){
ans += (1 << i);
x=y;
//cout<<L<<' '<<R<<'\n';
}
}
//cout<<x<<' '<<ans<<'\n';
if(h[x]>=h[mx2]) return ans+1;
if(h[o[0][x]]<=h[mx]) return ans+2;
//cout<<L<<' '<<R<<'\n';
for(int i = 19; i >= 0; i--){
int y=R[i][x];
//cout << nl << ' ' << nr << '\n';
if(y<C){
//cout<<y<<' '<<mx<<'\n';
ans += (1 << i);
x=y;
}
}
//cout<<x<<' '<<ans<<'\n';
//cout << r[0][R] << ' ' << r[0][L] << '\n';;
return ans+1;
}
/*
6 1
5 1 2 3 4 6
1 1 4 4
*/
