#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
int n, h[lim], L[lim], R[lim], up[lim][18];
bool is_sub1 = true;
void init(int __n, vector<int>__h){
n = __n;
stack<int>st;
for(int i = 0; i < n; st.push(i++)){
if((h[i] = __h[i]) != i + 1){
is_sub1 = false;
}
while(!st.empty() && h[st.top()] <= h[i]){
st.pop();
}
L[i] = (st.empty() ? -1 : st.top());
}
while(!st.empty()){
st.pop();
}
for(int i = n - 1; i > -1; st.push(i--)){
while(!st.empty() && h[st.top()] <= h[i]){
st.pop();
}
R[i] = (st.empty() ? -1 : st.top());
if(L[i] != -1 || R[i] != -1){
up[i][0] = (R[i] == -1 || (L[i] != -1 && h[L[i]] > h[R[i]]) ? L[i] : L[i]);
}
else{
up[i][0] = i;
}
}
for(int j = 1; j < 18; j++){
for(int i = 0; i < n; i++){
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D){
if(is_sub1){
return C - B;
}
if(n <= 2000){
queue<int>q;
vector<int>f(n, -1);
for(int i = A; i <= B; i++){
q.push(i);
f[i] = 0;
}
while(!q.empty()){
int u = q.front();
q.pop();
if(C <= u && D >= u){
return f[u];
}
if(L[u] != -1 && f[L[u]] == -1){
f[L[u]] = f[u] + 1;
q.push(L[u]);
}
if(R[u] != -1 && f[R[u]] == -1){
f[R[u]] = f[u] + 1;
q.push(R[u]);
}
}
}
else if(A == B && C == D){
if(h[A] < h[C]){
int ans = 0;
for(int i = 17; i > -1; i--){
if(h[up[A][i]] < h[C]){
A = up[A][i];
ans |= 1 << i;
}
}
return ans + 1;
}
}
return -1;
}
