#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 20;
pair<int, int> range[maxN];
pair<int, int> par[maxN];
int pos[maxN];
int ch[maxN][2];
int H[maxN];
int N;
int node_cnt;
int A, B, C, D;
int start_u;
int dfs1(int lt, int rt) {
if (lt > rt) {
return -1;
}
int u = node_cnt++;
range[u] = {lt, rt};
pair<int, int> mx = {H[lt], lt};
for (int i = lt; i <= rt; i++) {
mx = max(mx, make_pair(H[i], i));
}
int mt = mx.second;
pos[u] = mt;
ch[u][0] = dfs1(lt, mt - 1);
ch[u][1] = dfs1(mt + 1, rt);
if (ch[u][0] != -1) {
par[ch[u][0]] = {u, 0};
}
if (ch[u][1] != -1) {
par[ch[u][1]] = {u, 1};
}
return u;
}
void init(int _N, vector<int> _H) {
N = _N;
for (int i = 0; i < N; i++) {
H[i] = _H[i];
}
dfs1(0, N - 1);
}
void dfs3(int u) {
if (u == -1) {
return;
}
int mt = pos[u];
if (B < mt) {
dfs3(ch[u][0]);
}
else if (A > mt) {
dfs3(ch[u][1]);
}
else {
start_u = u;
return;
}
}
void dfs2(int u) {
if (u == -1) {
return;
}
int mt = pos[u];
if (D < mt) {
dfs2(ch[u][0]);
}
else if (C > mt) {
dfs2(ch[u][1]);
}
else {
dfs3(u);
}
}
int minimum_jumps(int _A, int _B, int _C, int _D) {
A = _A;
B = _B;
C = _C;
D = _D;
start_u = -1;
dfs2(0);
if (start_u == -1) {
return -1;
}
int prv = -1;
int streak = 0;
int cnt = 0;
int cur = start_u;
while (true) {
if (C <= pos[cur] && pos[cur] <= D) {
assert(prv == 0);
return (cnt - 1) / 2 + streak;
}
if (par[cur].second != prv) {
streak = 1;
cnt++;
}
else {
streak++;
}
prv = par[cur].second;
cur = par[cur].first;
}
return 0;
}
