#include "jumps.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
struct ST {
vector<pii> t;
ST(int N) {
t.assign(4*N+1,{0,0});
}
void update(int node,int l,int r,int p,pii v) {
if (l == r) {
t[node] = v;
return;
}
int m = (l+r) >> 1;
if (p <= m) update(2*node,l,m,p,v);
else update(2*node+1,m+1,r,p,v);
t[node] = max(t[2*node],t[2*node+1]);
}
pii query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return {0,0};
if (l >= L && r <= R) return t[node];
int m = (l+r) >> 1;
return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}
} st(200005);
int up[200005][20];
int n;
vector<int> hh;
void init(int N, std::vector<int> H) {
hh = H;
n = N;
st = ST(n);
for (int i=1;i<=N;i++) st.update(1,1,N,i,{H[i-1],i});
stack<int> stk;
for (int j = 0;j<20;j++) up[n+1][j] = n+1;
for (int i = N;i>=1;i--) {
while (!stk.empty() && H[stk.top()-1] < H[i-1]) stk.pop();
if (stk.empty()) up[i][0] = n+1;
else up[i][0] = stk.top();
stk.push(i);
}
for (int i=1;i<20;i++) {
for (int j = 1;j<=N;j++) up[j][i] = up[up[j][i-1]][i-1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++,B++,C++,D++;
if (up[B][0] > D) return -1;
if (B == C-1) return 1;
pii p1 = st.query(1,1,n,A,B);
pii p2 = st.query(1,1,n,C,D);
pii p3 = st.query(1,1,n,B+1,C-1);
if (p3.ff > p2.ff) return -1;
int select = 0;
for (int i = B;i>=A;i--) if (up[i][0] >= C && up[i][0] <= D) return 1;
for (int i = B;i>=A;i--) {
if (up[i][0] > B && up[i][0] <= D) select = i;
}
int p = select;
int steps = 0;
for (int i = 19;i>=0;i--) {
if (up[p][i] < C) {
steps+=(1<<i);
p = up[p][i];
}
}
return steps+1;
}
