#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
struct node{
int s,e,m;
int mx=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int i,int k){
if (s==e) mx=k;
else{
if (i<=m) l->update(i,k);
else r->update(i,k);
mx=max(l->mx,r->mx);
}
}
int query_mx(int i,int j){
if (s==i && e==j) return mx;
else if (j<=m) return l->query_mx(i,j);
else if (m<i) return r->query_mx(i,j);
else return max(l->query_mx(i,m),r->query_mx(m+1,j));
}
} *root=new node(0,200005);
int n;
int h[200005];
//when we jump to left/right where do we go to?
int l[200005];
int r[200005];
vector<int> proc;
int tkdl[200005][20];
int tkdr[200005][20];
int tkdlr[200005][20];
void init(int N, std::vector<int> H) {
n=N;
rep(x,0,n) h[x]=H[x];
rep(x,0,n) root->update(x,h[x]);
h[n]=1e9;
rep(x,0,n) l[x]=r[x]=n;
vector<int> stk;
rep(x,0,n){
while (!stk.empty() && h[stk.back()]<h[x]) stk.pob();
if (!stk.empty()) l[x]=stk.back();
stk.pub(x);
}
stk={};
rep(x,n,0){
while (!stk.empty() && h[stk.back()]<h[x]) stk.pob();
if (!stk.empty()) r[x]=stk.back();
stk.pub(x);
}
//rep(x,0,n) cout<<l[x]<<" "; cout<<endl;
//rep(x,0,n) cout<<r[x]<<" "; cout<<endl;
memset(tkdl,-1,sizeof(tkdl));
memset(tkdr,-1,sizeof(tkdr));
memset(tkdlr,-1,sizeof(tkdlr));
rep(x,0,n) proc.pub(x);
sort(all(proc),[](int i,int j){
return h[i]>h[j];
});
for (auto &it:proc){
if (l[it]==n) continue;
int curr=tkdl[it][0]=l[it];
rep(x,0,20){
if (curr==-1) continue;
curr=tkdl[it][x+1]=tkdl[curr][x];
}
}
for (auto &it:proc){
if (r[it]==n) continue;
int curr=tkdr[it][0]=r[it];
rep(x,0,20){
if (curr==-1) continue;
curr=tkdr[it][x+1]=tkdr[curr][x];
}
}
for (auto &it:proc){
int nxt;
if (h[l[it]]>h[r[it]]) nxt=l[it];
else nxt=r[it];
if (nxt==n) continue;
int curr=tkdlr[it][0]=nxt;
rep(x,0,20){
if (curr==-1) continue;
curr=tkdlr[it][x+1]=tkdlr[curr][x];
}
}
//rep(x,0,n) cout<<tkdlr[x][0]<<" "; cout<<endl;
}
int minimum_jumps(int a, int b, int c, int d) {
int lo,hi;
if (b+1==c) lo=-1;
else lo=root->query_mx(b+1,c-1);
hi=root->query_mx(c,d);
if (lo>hi) return -1;
if (h[b]>hi) return -1;
int curr=b;
rep(x,20,0){
//cout<<"debug: "<<curr<<" "<<x<<" "<<tkdl[curr][x]<<endl;
if (tkdl[curr][x]!=-1 && a<=tkdl[curr][x] && h[tkdl[curr][x]]<=hi){
curr=tkdl[curr][x];
}
}
//cout<<"debug: "<<curr<<endl;
int ans=0;
rep(x,20,0){
if (tkdlr[curr][x]!=-1 && h[tkdlr[curr][x]]<lo){
//cout<<curr<<" "<<tkdlr[curr][x]<<endl;
curr=tkdlr[curr][x];
ans+=(1<<x);
}
}
if (h[curr]<lo) if (tkdlr[curr][0]!=-1 && h[tkdlr[curr][0]]<=hi){
curr=tkdlr[curr][0];
ans++;
}
rep(x,20,0){
if (tkdr[curr][x]!=-1 && h[tkdr[curr][x]]<lo){
curr=tkdr[curr][x];
ans+=(1<<x);
}
}
if (h[curr]<lo){
ans++;
}
return ans+1;
}
