#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int B = 20;
int n;
vector<vector<int>> build(vector<vector<int>> g,vector<int>rt){
vector<vector<int>> up(n+1);
function<void(int,int )> dfs = [&](int v,int pr) {
up[v].resize(B);
up[v][0] = pr;
for(int i = 1;i < B;i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to:g[v]) {
dfs(to,v);
}
};
for(int i:rt) {
dfs(i,i);
}
return up;
}
vector<vector<int>> up,up1,up2;
const int maxn = (int)2e5 + 12;
int l[maxn],r[maxn];
vector<int> h;
bool te[maxn];
void init(int N, vector<int> H) {
h = H;
n = N;
vector<int> st,rt;
vector<vector<int>> G(n);
for(int i = 0;i < N;i++) {
while(!(int)st.empty() && H[st.back()] < H[i]) {
st.pop_back();
}
if(st.empty()){
rt.push_back(i);
l[i] = -1;
}else {
G[st.back()].push_back(i);
l[i] = st.back();
}
st.push_back(i);
}
up = build(G,rt);
for(int i = 0;i < n;i++){
G[i].clear();
}
rt.clear();
st.clear();
for(int i = N - 1;i >= 0;i--){
while(!st.empty() && H[st.back()] < H[i]){
st.pop_back();
}
if(st.empty()){
rt.push_back(i);
r[i] = -1;
}else {
G[st.back()].push_back(i);
r[i] = st.back();
}
st.push_back(i);
}
up1 = build(G,rt);
for(int i = 0;i < n;i++){
G[i].clear();
}
rt.clear();
int _x;
for(int i = 0;i < n;i++) {
if(l[i] == r[i] && l[i] == -1) {
_x = i;
break;
}
if(r[i] == -1) {
G[l[i]].push_back(i);
}else {
if(l[i] == -1 || H[l[i]] < H[r[i]]){
G[r[i]].push_back(i);
}else {
G[l[i]].push_back(i);
}
}
}
rt.push_back(_x);
up2 = build(G,rt);
}
int glob;
bool check(int ver,int C,int D){
int sum = 0;
for(int i = B - 1;i >= 0;i--){
if(up1[ver][i] < C){
ver = up1[ver][i];
sum += (1 << i);
}
}
sum++;;
glob = sum;
ver = up1[ver][0];
return (ver >= C && ver <= D);
}
int go(int ver,int C,int D) {
// return 1;
auto bad = [&](int x) -> bool {
if(!check(x,C,D)) return true;
if(x >= C && x <= D) return true;
if(r[x] >= C && r[x] <= D) return true;
return false;
};
int ans = 0;
for(int i = B - 1;i >= 0;i--) {
if(!bad(up2[ver][i])){
ver = up2[ver][i];
ans += (1 << i);
}
}
ans++;
ver = up2[ver][0];
check(ver,C,D);
// assert(check(ver,C,D));
ans += glob;
return ans;
}
int minimum_jumps(int A, int B, int C, int D) {
if(!check(B,C,D)) return -1;
int ver = B;
for(int i = 19;i >= 0;i--){
if(up[ver][i] >= A && check(up[ver][i],C,D)){
ver = up[ver][i];
}
}
if(r[ver] >= C && r[ver] <= D) return 1;
return go(ver,C,D);
}
