#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct solve{
int N;
vi H,Hinv;
vvi BL,BR;
solve(){}
solve(int N, vi H2) : N(N) {
map<int,int> mh;
for(int i = 0;i < N;i++) mh[H2[i]] = i;
H.assign(N,0);
Hinv = H;
for(int i = 0; auto [k,v] : mh){
H[v] = i;
Hinv[i] = v;
i++;
}
stack<int> st;
BL.assign(int(ceil(log2(N) + 2)),vi(N,-1));
BR = BL;
for(int i = 0;i < N;i++){
while(!st.empty() && H[st.top()] < H[i]) st.pop();
if(!st.empty()) BL[0][i] = st.top();
st.push(i);
}
st = {};
for(int i = N-1;i >= 0;i--){
while(!st.empty() && H[st.top()] < H[i]) st.pop();
if(!st.empty()) BR[0][i] = st.top();
st.push(i);
}
for(int p = 1;p < BL.size();p++){
for(int i = 0;i < N;i++){
if(BL[p-1][i] > BR[p-1][i]){
BL[p][i] = BL[p-1][BL[p-1][i]];
BR[p][i] = BR[p-1][BL[p-1][i]];
}
if(BL[p-1][i] < BR[p-1][i]){
BL[p][i] = BL[p-1][BR[p-1][i]];
BR[p][i] = BR[p-1][BR[p-1][i]];
}
}
}
}
int try_s(int S, int C, int D) {
int ans = 0;
int pos = S;
for(int p = BL.size() - 1;p >= 0;p--) {
if(BR[p][pos] == -1 || BR[p][pos] > D) continue;
ans += (1 << p);
pos = BR[p][pos];
if(pos >= C) break;
}
if(pos >= C) return ans;
return -1;
}
int query(int A, int B, int C, int D) {
int S = B;
int best = try_s(S,C,D);
int curr;
if(best == -1) return -1;
for(int p = BL.size()-1;p >= 0;p--) {
if(BL[p][S] < A) continue;
curr = try_s(BL[p][S],C,D);
if(curr > best) S = BL[p][S], best = curr;
}
return best;
}
};
solve So;
void init(int N, vi H) {
So = solve(N,H);
}
int minimum_jumps(int A, int B, int C, int D) {
return So.query(A,B,C,D);
}
