#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, L[maxn][20], R[maxn][20], up[maxn][20], up2[maxn][20], sub1 = 1;
vector<int> v;
void init(int N, vector<int> H) {
n = N;
v.push_back(1e9);
for(int &x : H) v.push_back(x);
v.push_back(1e9);
stack<pair<int, int> > st; st.push({ 1e9, 0 });
for(int i=1; i<=n; i++) {
if(v[i] != i) sub1 = 0;
while(!st.empty() && st.top().first <= v[i]) st.pop();
L[i][0] = st.top().second;
st.push({ v[i], i });
}
while(!st.empty()) st.pop();
st.push({ 1e9, n + 1 });
for(int i=n; i>=1; i--) {
while(!st.empty() && st.top().first <= v[i]) st.pop();
R[i][0] = st.top().second;
st.push({ v[i], i });
}
for(int j=1; j<20; j++)
for(int i=1; i<=n; i++) L[i][j] = L[L[i][j-1]][j-1];
for(int j=1; j<20; j++)
for(int i=1; i<=n; i++) R[i][j] = R[R[i][j-1]][j-1];
for(int i=1; i<=n; i++) {
if(L[i][0] == 0 && R[i][0] == n+1) up[i][0] = 0;
else if(L[i][0] == 0) up[i][0] = up2[i][0] = R[i][0];
else if(R[i][0] == 0) up[i][0] = up2[i][0] = L[i][0];
else {
up[i][0] = (v[L[i][0]] >= v[R[i][0]] ? L[i][0] : R[i][0]);
up2[i][0] = (v[L[i][0]] >= v[R[i][0]] ? R[i][0] : L[i][0]);
}
}
for(int j=1; j<20; j++)
for(int i=1; i<=n; i++) up[i][j] = up[up[i][j-1]][j-1];
for(int j=1; j<20; j++)
for(int i=1; i<=n; i++) up2[i][j] = up2[up2[i][j-1]][j-1];
}
int minimum_jumps(int A, int B, int C, int D) {
if(sub1) return C - B;
A++; B++; C++; D++;
if(A == B && C == D) {
if(v[A] > v[C]) return -1;
int ans = 0;
for(int i=19; i>=0; i--) {
if(up[A][i] == 0) continue;
if(v[up[A][i]] <= v[C]) ans += (1 << i), A = up[A][i];
}
if(v[A] > v[C]) return -1;
for(int i=19; i>=0; i--) {
if(up2[A][i] == 0) continue;
if(v[up2[A][i]] <= v[C]) ans += (1 << i), A = up2[A][i];
}
if(L[A][0] == C || R[A][0] == C) return ans + 1;
return (A == C ? ans : -1);
}
vector<int> dist(n+1), vis(n+1);
queue<int> q;
for(int i=A; i<=B; i++) vis[i] = 1, q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
if(C <= u && u <= D) return dist[u];
if(L[u][0] != 0 && !vis[L[u][0]]) {
vis[L[u][0]] = 1;
dist[L[u][0]] = dist[u] + 1;
q.push(L[u][0]);
}
if(R[u][0] != n + 1 && !vis[R[u][0]]) {
vis[R[u][0]] = 1;
dist[R[u][0]] = dist[u] + 1;
q.push(R[u][0]);
}
}
return -1;
}
