#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
int n;
vector<int> mx;
vector<int> mn;
SegmentTree() {}
SegmentTree(vector<int> a) : n(a.size()), mx(4 * n), mn(4 * n) {
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (l + 1 == r) {
mn[idx] = mx[idx] = a[l];
} else {
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
mn[idx] = min(mn[2 * idx + 1], mn[2 * idx + 2]);
mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
}
};
dfs(dfs, 0, 0, n);
}
int find(int ql, int qr, int ub, int rb) {
auto dfs = [&](auto self, int idx, int l, int r) -> int {
if (r <= ql || qr <= l) return -1;
if (ql <= l && r <= qr) return mx[idx];
int m = (l + r) >> 1;
return max(self(self, 2 * idx + 1, l, m), self(self, 2 * idx + 2, m, r));
};
return dfs(dfs, 0, 0, n);
}
};
const int LOG = 17;
int n;
vector<int> h, ih;
SegmentTree seg;
vector<vector<int>> f;
vector<int> depth;
void init(int N, vector<int> H) {
n = N;
h = H;
ih = vector<int>(n);
for (int i = 0; i < n; i++) {
h[i]--;
ih[h[i]] = i;
}
seg = SegmentTree(h);
h.push_back(n);
f = vector<vector<int>>(n + 1, vector<int>(LOG, n));
depth = vector<int>(n + 1, 0);
vector<int> stk = { n };
for (int i = n - 1; i >= 0; i--) {
while (h[stk.back()] < h[i]) stk.pop_back();
depth[i] = depth[stk.back()] + 1;
f[i][0] = stk.back();
stk.push_back(i);
}
stk.clear();
for (int i = 0; i < n; i++) {
while (!stk.empty() && h[stk.back()] < h[i]) stk.pop_back();
if (!stk.empty() && depth[stk.back()] <= depth[f[i][0]]) {
f[i][0] = stk.back();
}
stk.push_back(i);
}
for (int k = 1; k < LOG; k++) {
for (int i = 0; i < n; i++) {
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
}
int minimum_jumps(int l0, int r0, int l1, int r1) {
r0++; r1++;
int res = n;
for (int to = l1; to < r1; to++) {
int from = seg.find(l0, r0, h[to], to);
if (from == -1) continue;
from = ih[from];
int cnt = 0;
for (int k = LOG - 1; k >= 0; k--) {
int next = f[from][k];
if (depth[next] >= depth[to] && h[next] < h[to]) {
from = next;
cnt += 1 << k;
}
}
res = min(res, cnt + depth[from] - depth[to]);
}
if (res == n) return -1;
return res;
}
