#include "jumps.h"
#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
inline pi2 combine(const pi2 a, const pi2 b){
return {min(a.first,b.first),max(a.second,b.second)};
}
struct node{
int s,e,m;
node *l,*r;
pi2 v;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v({{0,0},{0,0}}){
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x, int y){
if(s==e){
v={{y,x},{y,x}};
return;
}
if(x<=m) l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
pi2 query(int x, int y){
if(x>y) return {{0,0},{0,0}};
if(x<=s&&y>=e){
return v;
}
if(y<=m) return l->query(x,y);
if(x>m) return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
}*root;
int n;
vector<int>adj[200005];
int dp[200005];
int dep[200005];
int two[21][200005];
int val[200005];
int two2[21][200005];
void dfs(int index, int par){
dp[index]=index;
for(int x=0;x<20;x++){
if(two[x][index]==-1) continue;
two[x+1][index]=two[x][two[x][index]];
}
for(auto it:adj[index]){
if(it==par) continue;
dep[it]=dep[index]+1;
two[0][it]=index;
dfs(it,index);
dp[index]=min(dp[index],dp[it]);
}
}
void init(int n2, vector<int>arr){
n=n2;
int lft[n+5];
int rgt[n+5];
memset(lft,-1,sizeof(lft));
memset(rgt,-1,sizeof(rgt));
memset(two,-1,sizeof(two));
memset(two2,-1,sizeof(two2));
vector<int>d;
int rt;
for(int x=0;x<n;x++){
while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
if(!d.empty()) lft[x]=d.back();
d.push_back(x);
}
d.clear();
for(int x=n-1;x>=0;x--){
while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
if(!d.empty()) rgt[x]=d.back();
d.push_back(x);
if(lft[x]==-1&&rgt[x]==-1) rt=x;
else if(lft[x]==-1) adj[rgt[x]].push_back(x);
else if(rgt[x]==-1) adj[lft[x]].push_back(x);
else if(arr[lft[x]]>arr[rgt[x]]) adj[lft[x]].push_back(x);
else adj[rgt[x]].push_back(x);
if(rgt[x]!=-1) two2[0][x]=rgt[x];
for(int y=0;y<20;y++){
if(two2[y][x]==-1) continue;
two2[y+1][x]=two2[y][two2[y][x]];
}
}
dfs(rt,-1);
root=new node(0,n+5);
for(int x=0;x<n;x++){
root->upd(x,arr[x]);
val[x]=arr[x];
}
}
int minimum_jumps(int a, int b, int c, int d){
//basic checking
int target=root->query(b+1,c-1).second.first;
int temp=root->query(c,d).second.first;
int best=-1;
int l=0;
int r=b;
int mid;
while(l<=r){
mid=(l+r)/2;
int hold=root->query(mid,b).second.first;
if(hold<=temp){
best=mid;
r=mid-1;
}
else l=mid+1;
}
if(best==-1||target>temp){
return -1;
}
int ans=0;
int cur=root->query(max(best,a),b).second.second;
for(int x=19;x>=0;x--){
int nxt=two[x][cur];
if(nxt==-1) continue;
if(dp[nxt]<best) continue;
if(val[nxt]>target) continue;
cur=nxt;
ans+=1<<x;
}
//case 1, go rgt
int add=0;
int st=cur;
for(int x=19;x>=0;x--){
int nxt=two2[x][st];
if(nxt==-1) continue;
if(nxt>=c) continue;
st=nxt;
add+=1<<x;
}
add++;
int add2=1e9;
if(two[0][cur]!=-1&&two[0][cur]>=best){
cur=two[0][cur];
int st=cur;
add2=0;
for(int x=19;x>=0;x--){
int nxt=two2[x][st];
if(nxt==-1) continue;
if(nxt>=c) continue;
st=nxt;
add2+=1<<x;
}
add2+=2;
}
return ans+min(add,add2);
}
