#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];
struct segTree{
int *st;
int n;
vector<int>ar;
void rupdate(int l, int r, int ind, int i){
if(i<l||i>r){
return;
}
if(l==r){
st[ind]=i;
return;
}
int mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i);
rupdate(mid+1,r,ind*2+2,i);
if(ar[st[ind*2+1]]>ar[st[2*ind+2]]){
st[ind]=st[ind*2+1];
}
else{
st[ind]=st[ind*2+2];
}
}
segTree(int siz, int arr[]){
int x = ceil(log2(siz));
x++;
st=new int[(1<<x)];
fill(st,st+(1<<x),0);
n=siz-1;
for(int i = 0;i<siz;i++){
ar.push_back(arr[i]);
}
for(int i = 0;i<siz;i++){
rupdate(0,n,0,i);
}
}
int rquery(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return -1;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
int lef = rquery(l,mid,s,e,ind*2+1);
int rig = rquery(mid+1,r,s,e,ind*2+2);
if(lef==-1){
return rig;
}
if(rig==-1){
return lef;
}
if(ar[lef]>ar[rig]){
return lef;
}
else{
return rig;
}
}
int query(int l, int r){
return rquery(0,n,l,r,0);
}
};
segTree st(maxn,h);
void init(int N, vector<int> H) {
n=N;
for(int i = 0;i<n;i++){
h[i]--;
h[i]=H[i];
rev[h[i]-1]=i;
}
st=segTree(n,h);
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;
int rig = -1;
if(it!=inds.end()){
g[ind].push_back(*it);
rig=*it;
}
if(it!=inds.begin()){
it--;
g[ind].push_back(*it);
lef=*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);
int leftmost = -1;
if(g[c].size()){
int cu = *min_element(g[c].begin(),g[c].end());
if(cu<c)
leftmost=cu;
}
leftmost++;
a=max(a,leftmost);
d=c;
if(a>b)
return -1;
a=st.query(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]){
ans+=(1<<i);
a=opt[a][i];
}
}
if(a!=opt[a][0]){
if(h[opt[a][0]]<=h[c]){
ans++;
a=opt[a][0];
}
}
//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]){
ans+=(1<<i);
a=nopt[a][i];
}
}
if(a!=nopt[a][0]){
if(h[nopt[a][0]]<=h[c]){
ans++;
a=nopt[a][0];
}
}
if(a!=c){
return -1;
}
//assert(ans!=0);
assert(ans<n);
return ans;
}
