#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<std::pair<int,int>> segtree[800010];
std::vector<int> dist;
std::vector<int> visit;
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 build(int c,int l,int r){
for(int i=l;i<=r;i++){
segtree[c].push_back({HG[i],i});
}
if(l==r)return;
std::sort(segtree[c].begin(),segtree[c].end());
int mid = (l+r)/2;
build(c*2,l,mid);
build(c*2+1,mid+1,r);
}
std::pair<int,int> query(int c,int l,int r,int ql,int qr,int max){
if(qr<l||ql>r)return {-1,-1};
if(ql<=l&&r<=qr){
std::pair<int,int> spair = {max,1e9};
int idx = (std::lower_bound(segtree[c].begin(),segtree[c].end(),spair)-segtree[c].begin())-1;
// std::cout << l << ' ' << r << '\n';
// std::cout << idx << '|';
// for(auto [l,r]:segtree[c]){
// std::cout << l << ' ' << r << '|';
// }
if(idx==-1)return {-1,-1};
//std::cout << segtree[c][idx].first << "->" << segtree[c][idx].second << '\n';
return segtree[c][idx];
}
int mid = (l+r)/2;
auto p1=query(c*2,l,mid,ql,qr,max);
auto p2=query(c*2+1,mid+1,r,ql,qr,max);
if(p1.first>p2.first)return p1;
else return p2;
}
void init(int N, std::vector<int> H) {
NG=N;
HG=H;
build(1,0,N-1);
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 C-B;
if(C==D){
int best=query(1,0,NG-1,A,B,HG[C]).second;
//std::cout << best << ' ';
if(best==-1)return -1;
return minDist(best,C);
}
std::queue<int> q;
dist.assign(NG,1e9);
visit.assign(NG,false);
for(int i=A;i<=B;i++)q.push(i),dist[i]=0,visit[i]=true;
while(!q.empty()){
int curr=q.front();q.pop();
for(auto to:adj[curr]){
if(visit[to])continue;
visit[to]=true;
dist[to]=dist[curr]+1;
q.push(to);
}
}
int min=1e9;
for(int i=C;i<=D;i++)min=std::min(dist[i],min);
if(min==1e9)min=-1;
return min;
}
