#include "jumps.h"
#include <bits/stdc++.h>
//good luck trying to read this (you will need it)
int NG;
std::vector<int> HG;
std::vector<int> adj[200010];
std::vector<int> rev[200010];
int highP[200010];
std::vector<int> revHigh[200010];
int biliftH[23][200010];
int depthH[200010];
int lowP[200010];
std::vector<int> revLow[200010];
int biliftL[23][200010];
int depthL[200010];
bool top[200010];
bool visitL[200010];
bool visitH[200010];
std::vector<int> dist;
void dfsH(int curr,int par){
//std::cout << curr << ' ';
if(visitH[curr])return;
visitH[curr]=true;
depthH[curr]=depthH[par]+1;
biliftH[0][curr]=par;
for(int i=1;i<=21;i++)biliftH[i][curr]=biliftH[i-1][biliftH[i-1][curr]];
for(auto to:revHigh[curr]){
if(to==par)continue;
dfsH(to,curr);
}
}
void dfsL(int curr,int par){
if(visitL[curr])return;
visitL[curr]=true;
depthL[curr]=depthL[par]+1;
biliftL[0][curr]=par;
for(int i=1;i<=21;i++)biliftL[i][curr]=biliftL[i-1][biliftL[i-1][curr]];
for(auto to:revLow[curr]){
if(to==par)continue;
dfsL(to,curr);
}
}
void init(int N, std::vector<int> H) {
NG=N;
HG=H;
std::stack<int> st;
int start=0,max=0;
for(int i=0;i<N;i++){
if(H[i]>max)start=i,max=H[i];
while(!st.empty()&&H[st.top()]<H[i])st.pop();
if(!st.empty())adj[i].push_back(st.top()),rev[st.top()].push_back(i);
st.push(i);
}
while(!st.empty())st.pop();
for(int i=N-1;i>=0;i--){
while(!st.empty()&&H[st.top()]<H[i])st.pop();
if(!st.empty())adj[i].push_back(st.top()),rev[st.top()].push_back(i);
st.push(i);
}
std::vector<std::pair<int,int>> order;
// for(int i=0;i<N;i++){
// for(auto num:adj[i])std::cout << num << ' ';
// std::cout << '\n';
// }
for(int i=0;i<N;i++){
if(adj[i].size()==0)top[i]=true,lowP[i]=-1,highP[i]=-1;
else if(adj[i].size()==1)lowP[i]=adj[i][0],highP[i]=adj[i][0],revLow[adj[i][0]].push_back(i),revHigh[adj[i][0]].push_back(i);
else{
if(H[adj[i][0]]>H[adj[i][1]]){
lowP[i]=adj[i][1];
revLow[adj[i][1]].push_back(i);
highP[i]=adj[i][0];
revHigh[adj[i][0]].push_back(i);
}
else{
lowP[i]=adj[i][0];
revLow[adj[i][0]].push_back(i);
highP[i]=adj[i][1];
revHigh[adj[i][1]].push_back(i);
}
}
order.push_back({H[i],i});
}
std::sort(order.rbegin(),order.rend());
for(auto [hei,i]:order){
dfsL(i,i);
dfsH(i,i);
//std::cout << '|';
}
}
int minDist(int from,int to){
if(HG[from]>HG[to])return -1;
int sum = 0;
int curr=from;
for(int i=21;i>=0;i--){
if(HG[biliftH[i][curr]]<=HG[to]){
sum+=depthH[curr]-depthH[biliftH[i][curr]];
curr=biliftH[i][curr];
}
// std::cout << curr << ' ';
}
if(curr==to)return sum;
for(int i=21;i>=0;i--){
if(HG[biliftL[i][curr]]<=HG[to]){
sum+=depthL[curr]-depthL[biliftL[i][curr]];
curr=biliftL[i][curr];
}
//std::cout << curr << ' ';
}
if(curr==to)return sum;
return -1;
}
int minimum_jumps(int A, int B, int C, int D) {
return minDist(A,C);
}
