#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 2e5;
constexpr int K = 18;
int jmp[N+9][K+1];
int jmpl[N+9][K+1];
int jmpr[N+9][K+1];
int h[N+9];
int l[N+9];
int r[N+9];
int dst[N+9];
int n;
constexpr int base = (1<<18);
pair<int,int> tree[2*base+9];
// min
pair<int,int> bet(pair<int,int> a, pair<int,int> b){
if (a.first>b.first)return a;
else return b;
}
pair<int,int> query(int x, int a, int b, int p, int k){
if (b<p || k<a)return {-1,0};
if (p<=a && b<=k){
return tree[x];
}
int mid=(a+b)/2;
return bet(query(2*x,a,mid,p,k),query(2*x+1,mid+1,b,p,k));
}
void init(int N, std::vector<int> H) {
n=N;
for (int x=0;x<n;x++)h[x]=H[x];
vector<pair<int,int>> stos; stos.push_back({2e9,n});
for (int x=0;x<n;x++){
while(h[x]>stos.back().first)stos.pop_back();
l[x]=stos.back().second;
stos.push_back({h[x],x});
}
h[n]=-2e9;
stos.clear(); stos.push_back({2e9,n});
for (int x=n-1;x>=0;x--){
while(h[x]>stos.back().first)stos.pop_back();
r[x]=stos.back().second;
stos.push_back({h[x],x});
}
for (int x=base;x<base+n;x++)tree[x]={h[x-base],x-base};
for (int x=base-1;x>=1;x--)tree[x]=bet(tree[2*x],tree[2*x+1]);
for (int x=0;x<n;x++){
if (h[l[x]]>h[r[x]])jmp[x][0]=l[x];
else jmp[x][0]=r[x];
jmpl[x][0]=l[x];
jmpr[x][0]=r[x];
}
jmp[n][0]=n;jmpl[n][0]=n; jmpr[n][0]=n;
for (int k=1;k<=K;k++){
for (int x=0;x<=n;x++){
jmp[x][k]=jmp[jmp[x][k-1]][k-1];
jmpl[x][k]=jmpl[jmpl[x][k-1]][k-1];
jmpr[x][k]=jmpr[jmpr[x][k-1]][k-1];
}
}
//for (int x=0;x<n;x++) cerr << jmp[x][0] << ' ';
//cerr << '\n';
/*for (int x=0;x<n;x++){
cerr << l[x] << ' ' << r[x] << '\n';
}*/
return;
}
int minimum_jumps(int A, int B, int C, int D){
if (C<=B && B<=D)return 0;
if (C<=A && A<=D)return 0;
if (A<=C && D<=B)return 0;
int mid=0;
if (C-B>1)mid=query(1,0,base-1,B+1,C-1).first;
if (A-D>1)mid=query(1,0,base-1,D+1,A-1).first;
int pocz= A; // TODO
int odp=0;
int kon = query(1,0,base-1,C,D).first;
for (int k=K;k>=0;k--){
if (h[jmp[pocz][k]]<mid && h[jmp[pocz][k]]!=-2e9 && h[jmp[pocz][k]]<=kon){
//cerr << pocz << " ->h " << jmp[pocz][k] << " koszt: " << (1<<k) << '\n';
odp+=(1<<k);
pocz=jmp[pocz][k];
}
}
while (h[pocz]<mid && pocz!=n && h[jmp[pocz][0]]<=kon){
//cerr << pocz << " -> " << jmp[pocz][0] << " koszt: 1\n";
pocz=jmp[pocz][0];
odp++;
}
if (pocz<C){
for (int k=K;k>=0;k--){
if (jmpr[pocz][k]<C){
//cerr << pocz << " ->r " << jmpr[pocz][k] << " koszt: " << (1<<k) << '\n';
odp+=(1<<k);
pocz=jmpr[pocz][k];
}
}
while(pocz<C){
odp++;
pocz=jmpr[pocz][0];
}
}
if (pocz>D){
for (int k=K;k>=0;k--){
if (jmpl[pocz][k]>D && jmpl[pocz][k]!=n){
//cerr << pocz << " ->l " << jmpl[pocz][k] << " koszt: " << (1<<k) << '\n';
odp+=(1<<k);
pocz=jmpl[pocz][k];
}
}
while(pocz>D && pocz!=n){
odp++;
pocz=jmpl[pocz][0];
}
}
if (C<=pocz && pocz<=D) return odp;
else return -1;
}
