#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int arr[200005],rev[200005];
struct node{
int s,e,m,v;
vector<int> dec;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;
if(s==e){
v=arr[s];
dec.pb(arr[s]);
}else{
l=new node(s,m);
r=new node(m+1,e);
v=max(l->v,r->v);
dec=l->dec;
while(!dec.empty()&&dec.back()<r->dec[0])dec.pop_back();
for(int i:(r->dec))dec.pb(i);
}
}
int rmaxq(int x,int y){
if(x>y)return -1;
if(s>=x&&e<=y)return v;
if(y<=m)return l->rmaxq(x,y);
if(x>m)return r->rmaxq(x,y);
return max(l->rmaxq(x,y),r->rmaxq(x,y));
}
int sminq(int x,int y){
if(s>=x&&e<=y)return dec.back();
if(y<=m)return l->sminq(x,y);
return r->sminq(x,y);
}
int sdecq(int x,int y,int val){ // largest value in the dec array that is <val
if(s>=x&&e<=y)return *(--lower_bound(dec.rbegin(),dec.rend(),val));
if(y<=m)return l->sdecq(x,y,val);
if(x>m)return r->sdecq(x,y,val);
int lres=l->sdecq(x,y,val),rmax=r->rmaxq(x,y);
if(lres>rmax)return lres;
return r->sdecq(x,y,val);
}
}*root;
int lrr[200005][20],rrr[200005][20];
int zoom[200005][20];
void init(int N, vector<int> H) {
for(int i=0;i<N;i++){
rev[H[i]]=i;
}
memset(lrr,-1,sizeof(lrr));
memset(rrr,-1,sizeof(rrr));
vector<ii> v;
for(int i=0;i<N;i++){
arr[i]=H[i];
while(!v.empty()&&v.back().fi<H[i])v.pop_back();
if(v.empty())lrr[i][0]=-1;
else lrr[i][0]=v.back().se;
v.pb(H[i],i);
}
v.clear();
for(int i=N-1;i>=0;i--){
while(!v.empty()&&v.back().fi<H[i])v.pop_back();
if(v.empty())rrr[i][0]=-1;
else rrr[i][0]=v.back().se;
v.pb(H[i],i);
}
for(int i=0;i<N;i++){
zoom[i][0]=(H[lrr[i][0]]>H[rrr[i][0]]?lrr[i][0]:rrr[i][0]);
}
root=new node(0,N-1);
for(int i=1;i<20;i++){
for(int j=0;j<N;j++){
if(lrr[j][i-1]!=-1)lrr[j][i]=lrr[lrr[j][i-1]][i-1];
else lrr[j][i]=-1;
if(rrr[j][i-1]!=-1)rrr[j][i]=rrr[rrr[j][i-1]][i-1];
else rrr[j][i]=-1;
if(zoom[j][i-1]!=-1)zoom[j][i]=zoom[zoom[j][i-1]][i-1];
else zoom[j][i]=-1;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int midmax=root->rmaxq(B+1,C-1),emax=root->rmaxq(C,D);
if(midmax>emax)return -1;
int smin=root->sminq(A,B);
if(smin>emax)return -1;
int start=root->sdecq(A,B,emax);
if(start>midmax)return 1;
int idx=rev[start];
int x1=idx,x2=idx;
// from start, "alternate" between inc(B+1,C-1) and dec(0,A-1) until
// reach midmax (then +1)
// exceed midmax (+1 if you are <emax, impossible if >emax)
int ans1=0;
for(int i=19;i>=0;i--){
if(zoom[x1][i]==-1)continue;
if(arr[zoom[x1][i]]<=midmax){
x1=zoom[x1][i];
ans1+=(1<<i);
//printf("%d %d\n",x1,ans1);
}
}
if(arr[x1]!=midmax){
ans1++;
}
int ans2=0;
for(int i=19;i>=0;i--){
if(zoom[x2][i]==-1)continue;
if(arr[zoom[x2][i]]<emax){
x2=zoom[x2][i];
ans2+=(1<<i);
//printf("%d %d\n",x2,ans2);
}
}
return min(ans1,ans2)+1;
}
