#include "jumps.h"
#include<iostream>
#include <vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
const int MAXN=200010, LOG=20;
int n, arr[MAXN], le[MAXN], ri[MAXN], upl[LOG][MAXN], ups[LOG][MAXN], sho[MAXN], lon[MAXN];
void init(int N, vector<int> H) {
n=N;
forn(i, n) arr[i]=H[i]-1;
le[0]=-1;
ri[n-1]=n;
forn(i, n-1){
int cur=i;
while(cur!=-1 && arr[cur]<arr[i+1]) cur=le[cur];
le[i+1]=cur;
}
dforn(i, n-1){
int cur=i+1;
while(cur!=n && arr[cur]<arr[i]) cur=ri[cur];
ri[i]=cur;
}
arr[n]=sho[n]=lon[n]=n;
forn(i, n){
if(arr[i]==n-1) sho[i]=lon[i]=n;
else{
int a=le[i], b=ri[i];
if(a==-1) lon[i]=sho[i]=b;
else if(b==n) lon[i]=sho[i]=a;
else if(arr[a]>arr[b]) lon[i]=a, sho[i]=b;
else lon[i]=b, sho[i]=a;
}
}
forn(i, n+1) upl[0][i]=lon[i], ups[0][i]=sho[i];
forn(i, LOG-1) forn(j, n+1) upl[i+1][j]=upl[i][upl[i][j]];
forn(i, LOG-1) forn(j, n+1) ups[i+1][j]=ups[i][ups[i][j]];
}
int minimum_jumps(int A, int B, int C, int D) {
int cur=A, ans=0;
dforn(i, LOG) if(arr[upl[i][cur]]<=arr[C]) cur=upl[i][cur], ans+=(1<<i);
dforn(i, LOG) if(arr[ups[i][cur]]<=arr[C]) cur=ups[i][cur], ans+=(1<<i);
return cur==C? ans : -1;
}
