#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 20;
const int maxL = 20;
int lg[maxN];
pair<int, int> range[maxN];
pair<int, int> sparse[maxN][maxL];
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, fin;
int time_in[maxN];
int time_out[maxN];
pair<int, int> jump[maxN][maxL];
int T;
int get(int lt, int rt) {
int k = lg[rt - lt + 1];
return max(sparse[lt][k], sparse[rt - (1 << k) + 1][k]).second;
}
int dfs1(int lt, int rt) {
if (lt > rt) {
return -1;
}
int u = node_cnt++;
range[u] = {lt, rt};
int mt = get(lt, rt);
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;
}
if (ch[u][1] != -1) {
par[ch[u][1]] = u;
}
return u;
}
void dfs4(int u, int cur_0, int cur_1) {
time_in[u] = ++T;
if (ch[u][0] != -1) {
jump[ch[u][0]][0] = {cur_1, max(pos[ch[u][0]], pos[u])};
dfs4(ch[u][0], u, cur_1);
}
if (ch[u][1] != -1) {
jump[ch[u][1]][0] = {cur_0, max(pos[ch[u][1]], pos[u])};
dfs4(ch[u][1], cur_0, u);
}
time_out[u] = ++T;
}
bool anc(int u, int v) {
return (u != -1 && v != -1) && (time_in[u] <= time_in[v] && time_out[v] <= time_out[u]);
}
void init(int _N, vector<int> _H) {
for (int i = 2; i < maxN; i++) {
lg[i] = lg[i / 2] + 1;
}
N = _N;
for (int i = 0; i < N; i++) {
H[i] = _H[i];
sparse[i][0] = {H[i], i};
}
for (int k = 1; k < maxL; k++) {
for (int i = 0; i + (1 << k) <= N; i++) {
sparse[i][k] = max(sparse[i][k - 1], sparse[i + (1 << (k - 1))][k - 1]);
}
}
dfs1(0, N - 1);
dfs4(0, -1, -1);
jump[0][0] = {-1, -1};
for (int k = 1; k < maxL; k++) {
for (int u = 0; u < N; u++) {
int v = jump[u][k - 1].first;
if (v == -1) {
jump[u][k] = {-1, -1};
}
else {
jump[u][k] = {jump[v][k - 1].first, max(jump[u][k - 1].second, jump[v][k - 1].second)};
}
}
}
}
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;
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 {
fin = u;
dfs3(u);
}
}
int minimum_jumps(int _A, int _B, int _C, int _D) {
A = _A;
B = _B;
C = _C;
D = _D;
start = -1;
fin = -1;
dfs2(0);
if (start == -1 || fin == -1) {
return -1;
}
int cur = start;
int res = 0;
for (int k = maxL - 1; k >= 0; k--) {
int nxt = jump[cur][k].first;
int mx = jump[cur][k].second;
if (C > mx && anc(fin, nxt)) {
cur = nxt;
res += (1 << k);
}
}
while (C > pos[cur]) {
cur = par[cur];
res++;
}
return res;
}
