#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int lg = 22;
int h[maxn];
vector<int>g[maxn];
int rev[maxn];
int n;
int opt[maxn][lg];
int nopt[maxn][lg];
void init(int N, vector<int> H) {
n=N;
for(int i = 0;i<n;i++){
h[i]=H[i];
rev[h[i]-1]=i;
}
for(int i = 0;i<n;i++){
fill(opt[i],opt[i]+lg,i);
fill(nopt[i],nopt[i]+lg,i);
}
set<int>inds;
for(int i = n-1;i>=0;i--){
int ind = rev[i];
if(inds.size()){
auto it = inds.lower_bound(ind);
int lef = -1;
if(it!=inds.end()){
g[ind].push_back(*it);
lef=*it;
}
int rig = -1;
if(it!=inds.begin()){
it--;
g[ind].push_back(*it);
rig=*it;
}
if(lef==-1&&rig!=-1){
//opt and nopt both go right
opt[ind][0]=rig;
nopt[ind][0]=rig;
for(int i = 1;i<lg;i++){
opt[ind][i]=opt[opt[ind][i-1]][i-1];
nopt[ind][i]=nopt[nopt[ind][i-1]][i-1];
}
}
if(lef!=-1&&rig==-1){
//opt and nopt both go right
opt[ind][0]=lef;
nopt[ind][0]=lef;
for(int i = 1;i<lg;i++){
opt[ind][i]=opt[opt[ind][i-1]][i-1];
nopt[ind][i]=nopt[nopt[ind][i-1]][i-1];
}
}
if(lef!=-1&&rig!=-1){
//now must see
if(h[lef]<h[rig]){
swap(lef,rig);
}
//now lef is opt rig is nopt
opt[ind][0]=lef;
nopt[ind][0]=rig;
for(int i = 1;i<lg;i++){
opt[ind][i]=opt[opt[ind][i-1]][i-1];
nopt[ind][i]=nopt[nopt[ind][i-1]][i-1];
}
}
}
inds.insert(rev[i]);
}
//graph creation done
//kth ancestor shenanigans done
}
int minimum_jumps(int a, int b, int c, int d) {
int ans = 0;
//assert(a==b&&c==d);
a=b;
//assuming a=b,c=d
//a will traverse rn
for(int i = lg-1;i>=0;i--){
if(h[opt[a][i]]>h[c]){
continue;
}
else{
if(i&&opt[a][i]==opt[a][i-1])
continue;
if(i==0&&opt[a][i]==a)
continue;
ans+=(1<<i);
assert(a!=opt[a][i]);
a=opt[a][i];
//cout << "going to: " << a << " " << i << "\n";
}
}
//cout << "opt done\n";
//a is at best position, now nopts must occur
for(int i = lg-1;i>=0;i--){
if(h[nopt[a][i]]>h[c]){
continue;
}
else{
if(i&&nopt[a][i]==nopt[a][i-1])
continue;
if(i==0&&nopt[a][i]==a)
continue;
ans+=(1<<i);
assert(a!=nopt[a][i]);
a=nopt[a][i];
//cout << "going to: " << a << " " << i << "\n";
}
}
if(a!=c){
return -1;
}
return ans;
}
