#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200001, logn = 20;
int t[maxn * 4], t2[maxn * 4], up[maxn][logn], up2[maxn][logn];
vector<int> h;
void update(int v, int tl, int tr, int i, int x) {
if (tl == tr - 1) {
t[v] = x;
t2[v] = tl;
} else {
int tm = (tl + tr) / 2;
if (i < tm) update(2*v + 1, tl, tm, i, x);
else update(2*v + 2, tm, tr, i, x);
t[v] = max(t[2*v + 1], t[2*v + 2]);
if (t[2*v + 1] > t[2*v + 2]) t2[v] = t2[2*v + 1];
else t2[v] = t2[2*v + 2];
}
}
pair<int, int> query(int v, int tl, int tr, int l, int r) {
if (l >= r) return {0, 0};
else if (tl == l && tr == r) return {t[v], t2[v]};
else {
int tm = (tl + tr) / 2;
auto r1 = query(2*v + 1, tl, tm, l, min(r, tm));
return max(r1, query(2*v + 2, tm, tr, max(l, tm), r));
}
}
int n;
void init(int N, std::vector<int> H) {
n = N;
h = H;
n++;
h.push_back(n + 1);
for (int i = 0; i < n; i++) update(0, 0, n, i, h[i]);
vector<pair<int, int>> b;
for (int i = 0; i < n; i++) b.emplace_back(h[i], i);
sort(b.rbegin(), b.rend());
for (auto tp: b) {
int i = tp.second;
int g1 = i, g2 = i;
{
int lb = 0, ub = i - 1;
while (lb <= ub) {
int tm = (lb + ub) / 2;
auto r = query(0, 0, n, tm, i + 1);
if (r.second != i) {
g1 = r.second;
lb = tm + 1;
} else {
ub = tm - 1;
}
}
}
{
int lb = i + 1, ub = n - 1;
while (lb <= ub) {
int tm = (lb + ub) / 2;
auto r = query(0, 0, n, i, tm + 1);
if (r.second != i) {
g2 = r.second;
ub = tm - 1;
} else {
lb = tm + 1;
}
}
}
if (h[g2] > h[g1]) swap(g2, g1);
up[i][0] = g1;
up2[i][0] = g2;
for (int j = 1; j < logn; j++) {
up[i][j] = up[up[i][j - 1]][j - 1];
up2[i][j] = up2[up2[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int x = query(0, 0, n, C, D + 1).first;
int y = query(0, 0, n, B + 1, C).first;
if (y >= x) return -1;
int lb = A, ub = B, tans = -1;
while (lb <= ub) {
int tm = (lb + ub) / 2;
if (query(0, 0, n, tm, B + 1).first < x) {
tans = tm;
ub = tm - 1;
} else {
lb = tm + 1;
}
}
if (tans == -1) return -1;
int v = query(0, 0, n, tans, B + 1).second;
int ans = 0;
for (int i = logn - 1; i >= 0; i--) {
if (h[up[v][i]] <= y) {
v = up[v][i];
ans += (1 << i);
}
}
if (h[v] < y && up[v][0] <= y) {
ans++;
v = up[v][0];
}
if (h[up[v][0]] < x) {
return ans + 1;
}
for (int i = logn - 1; i >= 0; i--) {
if (h[up2[v][i]] <= y) {
v = up2[v][i];
ans += (1 << i);
}
}
if (h[v] < y && up2[v][0] <= y) {
ans++;
v = up2[v][0];
}
return ans + 1;
}
