#include "jumps.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5+5;
int r[N],l[N],n,dist[N],F,ans,aft[2][N][20],Lg,a[N],tree[4*N],idx[N];
vector<int>V[N];
void build(int u,int l,int r){
if(l==r) {
tree[u] = a[l];
return;
}
int mid=(l+r)/2;
build(2*u,l,mid);
build(2*u+1,mid+1,r);
tree[u] = max(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r){
if(l>end || r<start) return 0;
if(start<=l && r<=end) return tree[u];
int mid = (l+r)/2;
return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
void init(int NN, std::vector<int> H) {
n=NN;
for(int i=0;i<n;i++){
aft[0][i][0] = -1;
aft[1][i][0] = -1;
a[i]=H[i];
idx[a[i]] = i;
int x = i-1;
if(H[i]!=i+1) F=1;
while(x>=0 && H[x]<=H[i]) x = l[x];
l[i] = x;
if(x>=0) V[i].push_back(x);
}
build(1,0,n-1);
for(int i=n-1;i>=0;i--){
int x = i+1;
while(x<n && H[x]<H[i]) x = r[x];
r[i] = x;
if(x<n) V[i].push_back(x);
if(r[i]<n && l[i]>=0) {
aft[1][i][0] = r[i];
aft[0][i][0] = l[i];
if(H[r[i]] < H[l[i]]) swap(aft[1][i][0],aft[0][i][0]);
}
else if(r[i]<n) {
aft[1][i][0] = r[i];
}
else if(l[i]>=0){
aft[1][i][0] = l[i];
}
}
Lg = log2(n)+1;
for(int f=0;f<2;f++){
for(int j=1;j<=Lg;j++)
for(int i=0;i<n;i++) {
if(aft[f][i][j-1]==-1) aft[f][i][j] = -1;
else aft[f][i][j]=aft[f][aft[f][i][j-1]][j-1];
}
}
}
int Up(int u,int f,int b){
for(int i=Lg;i>=0;i--){
if(aft[f][u][i]!=-1 && a[aft[f][u][i]] <= b ) ans += (1<<i),u=aft[f][u][i];
}
return u;
}
int minimum_jumps(int A, int B, int C, int D) {
if(!F) {
if(A>D ) return -1;
if(B<=C) return C-B;
return 0;
}
else if( C==D){
ans = 0;
if(A<=C && C<=B) return 0;
if(B<C) {
if(l[D] >= B) return -1;
A = getans(1,max(A,l[D]+1),B,0,n-1);
}
else {
if(r[D] <= A) return -1;
A= getans(1,A,min(B,r[D]-1),0,n-1);
}
A = idx[A];
if(Up(Up(A,1,a[C]),0,a[C]) == C) return ans;
return -1;
}
else {
queue<pii>q;
int Inf=n+5;
for(int i=0;i<n;i++) dist[i] = Inf;
for(int i=A;i<=B;i++){
q.push({0,i});
dist[i] = 0;
}
int ans=Inf;
while(q.size()){
int u = q.front().s;
int d=q.front().f;
q.pop();
if(d>dist[u]) continue;
if(u>=C && u<=D) ans=min(ans,d);
for(int i=0;i<V[u].size();i++) {
if(dist[V[u][i]]>d+1){
dist[V[u][i]]=d+1;
q.push({d+1,V[u][i]});
}
}
}
if(ans!=Inf) return ans;
return -1;}
}
