#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;
}
vector<int> bloki;
bool rob=0;
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){
if (rob) bloki.push_back(x);
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));
}
int zejdz(int x, int cel){
if (x>=base)return x-base;
if (tree[2*x+1].first>=cel)return zejdz(2*x+1,cel);
return zejdz(2*x,cel);
}
int zejdz2(int x, int cel){
if (x>=base)return x-base;
if (tree[2*x].first>=cel)return zejdz2(2*x,cel);
return zejdz2(2*x+1,cel);
}
int dist(int pocz, int C, int D){
int odp=0;
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){
//cerr << pocz << " ->r " << jmpr[pocz][0] << " koszt: 1\n";
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){
//cerr << pocz << " ->l " << jmpl[pocz][0] << " koszt: 1\n";
odp++;
pocz=jmpl[pocz][0];
}
}
if (pocz==n)return 1e9;
if (!(C<=pocz && pocz<=D)) return 1e9;
return odp;
}
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= -1; // TODO
rob=1;
bloki.clear();
int odp2=1e9;
if (query(1,0,base-1,A,B).first<mid){
rob=0;
pocz=query(1,0,base-1,A,B).second;
}
else{
if (A<C){
for (int x=bloki.size()-1;x>=0;x--){
if (tree[bloki[x]].first>=mid){
pocz = zejdz(bloki[x],mid);
}
}
odp2 = dist(pocz,C,D);
pocz++;
if (pocz==B+1)pocz=B;
}
else{
for (int x=0;x<bloki.size();x++){
if (tree[bloki[x]].first>=mid){
pocz = zejdz2(bloki[x],mid);
}
}
odp2=dist(pocz,C,D);
pocz--;
if (pocz==A-1)pocz=A;
}
}
rob=0;
//cerr << mid << ' ' << pocz << '\n';
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 << " ->h " << jmp[pocz][0] << " koszt: 1\n";
pocz=jmp[pocz][0];
odp++;
}
odp+=dist(pocz,C,D);
//cerr << odp << ' ' << odp2 << '\n';
if (min(odp,odp2)==1e9) return -1;
return min(odp,odp2);
}
