#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,BRR,BLL;
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));
BLL = BRR = 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);
}
BRR[0] = BR[0];
BLL[0] = BL[0];
for(int p = 1;p < BL.size();p++){
for(int i = 0;i < N;i++){
int hl = (BL[p-1][i] == -1 ? -1 : H[BL[p-1][i]]);
int hr = (BR[p-1][i] == -1 ? -1 : H[BR[p-1][i]]);
if(hl > hr){
BL[p][i] = BL[p-1][BL[p-1][i]];
BR[p][i] = BR[p-1][BL[p-1][i]];
if(BR[p][i] == -1 && hr != -1) BR[p][i] = BR[p-1][BR[p-1][i]];
}
if(hl < hr){
BL[p][i] = BL[p-1][BR[p-1][i]];
if(BL[p][i] == -1 && hl != -1) BL[p][i] = BL[p-1][BL[p-1][i]];
BR[p][i] = BR[p-1][BR[p-1][i]];
}
if(BRR[p-1][i] != -1) BRR[p][i] = BRR[p-1][BRR[p-1][i]];
if(BLL[p-1][i] != -1) BLL[p][i] = BLL[p-1][BLL[p-1][i]];
}
}
}
bool is_pos(int S, int C, int D) {
if(S == -1 || S > D) return 0;
int pos = S;
for(int p = BRR.size() - 1;p >= 0;p--) {
if(BRR[p][pos] == -1 || BRR[p][pos] > D) continue;
pos = BRR[p][pos];
if(pos >= C) break;
}
if(pos >= C) return 1;
return 0;
}
int try_s(int S, int C, int D) {
int ans = 0;
int pos = S;
if(!is_pos(S,C,D)) return -1;
for(int p = BL.size() - 1;p >= 0;p--) {
if(BR[p][pos] >= C || BR[p][pos] == -1) continue;
if(BL[p][pos] != -1 && H[BL[p][pos]] > H[BR[p][pos]] && is_pos(BL[p][pos],C,D)){
ans += (1 << p);
pos = BL[p][pos];
}
else if(is_pos(BR[p][pos],C,D)){
ans += (1 << p);
pos = BR[p][pos];
}
}
return ans + 1;
}
int query(int A, int B, int C, int D) {
int S = B;
for(int p = BLL.size()-1;p >= 0;p--) {
if(BLL[p][S] < A) continue;
if(is_pos(BLL[p][S],C,D)) S = BLL[p][S];
}
return try_s(S,C,D);
}
};
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);
}
