#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAX_N=2e5+10;
const int MAX_P=MAX_N*4;
int st[MAX_P];
int val[MAX_N];
int n;
vector<vi> lo,hi;
void init_tr(int node,int a,int b){
if(a==b){
st[node]=val[a];
return;
}
int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
init_tr(le,a,mid);
init_tr(ri,mid+1,b);
st[node]=max(st[le],st[ri]);
}
int query(int node,int a,int b,int l,int r){
if(b<l || a>r) return 0;
if(l<=a && r>=b) return st[node];
int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
return max(query(le,a,mid,l,r),query(ri,mid+1,b,l,r));
}
int izquier(int x){
int q=query(0,0,n-1,0,x);
if(q==val[x]) return -1;
int l=0,r=x;
while(r-l>1){
int mid=(l+r)/2;
q=query(0,0,n-1,mid,r);
if(q>val[x])
l=mid;
else r=mid;
}
return l;
}
int derecha(int x){
int q=query(0,0,n-1,x,n-1);
if(q==val[x]) return -1;
int l=x,r=n-1;
while(r-l>1){
int mid=(l+r)/2;
q=query(0,0,n-1,l,mid);
if(q>val[x]) r=mid;
else l=mid;
}
return r;
}
int sh[MAX_N][32];
int sl[MAX_N][32];
bool vis[MAX_N];
void low_edge(int u,int p,int he){
if(he>=1){
sl[u][0]=p;
for(int i=1;i<30;i++){
if((1<<i)>he) break;
sl[u][i]=sl[sl[u][i-1]][i-1];
}
}
vis[u]=1;
for(auto &v:lo[u]){
if(!vis[v] && v!=p){
low_edge(v,u,he+1);
}
}
}
void high_edge(int u,int p,int he){
if(he>=1){
sh[u][0]=p;
for(int i=1;i<30;i++){
if((1<<i)>he) break;
sh[u][i]=sh[sh[u][i-1]][i-1];
}
}
vis[u]=1;
for(auto &v:hi[u]){
if(!vis[v] && v!=p){
high_edge(v,u,he+1);
}
}
}
int ih[MAX_N],il[MAX_N];
void init(int N, std::vector<int> H) {
for(int i=0;i<N;i++) val[i]=H[i];
hi.resize(N+1);
lo.resize(N+1);
n=N;
memset(ih,0,sizeof ih);
memset(il,0,sizeof il);
init_tr(0,0,n-1);
for(int i=0;i<n;i++){
int l=izquier(i);
int r=derecha(i);
if(r!=-1 && l!=-1){
if(val[r]>val[l]){
hi[r].push_back(i);
lo[l].push_back(i);
}
else{
hi[l].push_back(i);
lo[r].push_back(i);
}
ih[i]++; il[i]++;
}
else{
if(l!=-1) lo[l].push_back(i);
if(r!=-1) lo[r].push_back(i);
if(l!=-1 || r!=-1) il[i]++;
}
}
memset(vis,0,sizeof vis);
memset(sl,-1,sizeof sl);
memset(sh,-1,sizeof sh);
for(int i=n-1;i>=0;i--){
if(!il[i]) low_edge(i,i,0);
}
memset(vis,0,sizeof vis);
for(int i=n-1;i>=0;i--){
if(!ih[i]) high_edge(i,i,0);
}
}
int minimum_jumps(int A, int B, int C, int D) {
int res=0;
for(int i=29;i>=0;i--){
if(sh[A][i]!=-1 && val[sh[A][i]]<val[C]){
A=sh[A][i];
res+=(1<<i);
}
}
if(val[sh[A][0]]==val[C]) return res+1;
for(int i=29;i>=0;i--){
if(sl[A][i]!=-1 && val[sl[A][i]]<val[C]){
A=sl[A][i];
res+=(1<<i);
}
}
if(val[sl[A][0]]==val[C]) return res+1;
return -1;
}
