#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 2e5;
int h[N+9];
int l[N+9];
int r[N+9];
int dst[N+9];
int n;
constexpr int base = (1<<18);
int tree[2*base+9];
// min
void sed(int x, int a, int b, int p, int k, int val){
if (b<p || k<a)return;
if (p<=a && b<=k){
tree[x]=min(tree[x],val);
return;
}
int mid=(a+b)/2;
sed(2*x,a,mid,p,k,val);
sed(2*x+1,mid+1,b,p,k,val);
}
int query(int x){
x+=base;
int odp=1e9;
while(x){
odp=min(odp,tree[x]);
x/=2;
}
return odp;
}
bool stupido=1;
void init(int N, std::vector<int> H) {
n=N;
for (int x=0;x<n;x++){
if (H[x]!=x+1)stupido=0;
}
for (int x=0;x<n;x++)h[x]=H[x];
for (int x=0;x<=2*base+2;x++)tree[x]=1e9;
for (int x=n-1;x>=0;x--){
r[x]=query(h[x]);
sed(1,0,base-1,0,h[x],x);
}
for (int x=0;x<=2*base+2;x++)tree[x]=1e9;
for (int x=0;x<n;x++){
l[x]=-query(h[x]);
sed(1,0,base-1,0,h[x],-x);
}
/*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 (stupido){
int odp = 1e9;
odp = min(odp,min(abs(A-C),abs(B-C)));
odp = min(odp,min(abs(A-D),abs(B-D)));
if (C<=B && B<=D)odp=0;
if (C<=A && A<=D)odp=0;
if (A<=C && D<=B)odp=0;
return odp;
}
if (A==B && C==D && 1==0){
int odp=0;
while(A!=C){
if (A<C){
A=r[A];
odp++;
}
else if (A>C){
A=l[A];
odp++;
}
if (A==-1e9 || A==1e9){
odp=-1;
break;
}
}
return odp;
}
vector<int> kol;
for (int x=0;x<n;x++)dst[x]=1e9;
for (int x=A;x<=B;x++){
dst[x]=0;
kol.push_back(x);
}
for (int y=0;y<(int)kol.size();y++){
if (C<=kol[y] && kol[y]<=D)return dst[kol[y]];
if (l[kol[y]]!=-1e9){
if (dst[l[kol[y]]]>dst[kol[y]]+1){
dst[l[kol[y]]]=dst[kol[y]]+1;
kol.push_back(l[kol[y]]);
}
}
if (r[kol[y]]!=1e9){
if (dst[r[kol[y]]]>dst[kol[y]]+1){
dst[r[kol[y]]]=dst[kol[y]]+1;
kol.push_back(r[kol[y]]);
}
}
}
return -1;
}
