#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());
int n;
vector<int>lft[200005];
vector<int>rgt[200005];
bool visited[200005];
int two[21][200005];
int dep[200005];
int two2[21][200005];
int val[21][200005];
int dep2[200005];
void dfs2(int index, int par){
visited[index]=true;
for(int x=0;x<20;x++){
if(two2[x][index]==-1) continue;
two2[x+1][index]=two2[x][two2[x][index]];
}
for(auto it:rgt[index]){
if(it==par) continue;
dep2[it]=dep2[index]+1;
two2[0][it]=index;
dfs2(it,index);
}
}
void dfs(int index, int par){
visited[index]=true;
for(int x=0;x<20;x++){
if(two[x][index]==-1) continue;
two[x+1][index]=two[x][two[x][index]];
val[x+1][index]=max(val[x][index],val[x][two[x][index]]);
}
for(auto it:lft[index]){
if(it==par) continue;
dep[it]=dep[index]+1;
two[0][it]=index;
val[0][it]=dep2[index]-dep[index];
dfs(it,index);
}
}
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 storage[200005];
void init(int n2, vector<int>arr){
n=n2;
vector<int>d;
for(int x=0;x<n;x++){
storage[x]=arr[x];
while(!d.empty()&&arr[d.back()]<arr[x]){
d.pop_back();
}
if(!d.empty()){
lft[x].push_back(d.back());
lft[d.back()].push_back(x);
}
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].push_back(d.back());
rgt[d.back()].push_back(x);
}
d.push_back(x);
}
memset(two,-1,sizeof(two));
memset(two2,-1,sizeof(two2));
for(int x=n-1;x>=0;x--){
if(visited[x]) continue;
dfs2(x,-1);
}
memset(visited,0,sizeof(visited));
for(int x=0;x<n;x++){
if(visited[x]) continue;
dfs(x,-1);
}
root=new node(0,n+5);
for(int x=0;x<n;x++){
root->upd(x,arr[x]);
}
}
int f(int l2, int a, int b, int c, int d, int mid2){
int best=d;
int l=c;
int r=d;
int mid;
while(l<=r){
mid=(l+r)/2;
if(root->query(c,mid).second.first>mid2){
best=mid;
r=mid-1;
}
else l=mid+1;
}
int cur=root->query(a,b).second.second;
int st=cur;
int offset=dep[cur]-dep2[best];
int hold=1e9;
for(int x=19;x>=0;x--){
if(two[x][cur]==-1) continue;
if(two[x][cur]<l2) continue;
if(storage[two[x][cur]]>mid) continue;
hold=min(hold,val[x][cur]);
cur=two[x][cur];
}
hold+=offset;
if(two[0][cur]!=-1&&storage[two[0][cur]]>=l2){
hold=min(hold,1+dep[st]-dep[cur]);
}
return hold;
}
int minimum_jumps(int a, int b, int c, int d){
//basic checking
int midd=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||midd>temp){
return -1;
}
//go right
int cur=root->query(max(a,best),b).second.second;
int ans=0;
for(int x=19;x>=0;x--){
if(two2[x][cur]==-1) continue;
if(two2[x][cur]<c){
cur=two2[x][cur];
ans+=1<<x;
}
}
ans++;
//go left then right
if(best<a-1){
ans=min(ans,f(best,a,b,c,d,midd));
}
return ans;
}
