#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;
const int LOG = 18;
const int N = 2e5 + 5;
int a[N], id[N];
int l[N], r[N];
int lo[LOG][N], hi[LOG][N];
// SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> mat;
F func;
void build(const vector<T>& arr, const F& f) {
func = f;
n = static_cast<int>(arr.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = arr;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int from, int to) const {
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
SparseTable<int> spa;
void init(int N_, std::vector<int> H) {
stack<int> stk;
for (int i = 1; i <= N_; ++i) {
a[i] = H[i - 1];
}
for (int i = 1; i <= N_; ++i) {
while (!stk.empty() && a[stk.top()] < a[i]) {
stk.pop();
}
if (!stk.empty()) {
l[i] = stk.top();
}
stk.push(i);
}
while (!stk.empty()) {
stk.pop();
}
for (int i = N_; i >= 1; --i) {
while (!stk.empty() && a[stk.top()] < a[i]) {
stk.pop();
}
if (!stk.empty()) {
r[i] = stk.top();
}
stk.push(i);
hi[0][i] = (a[l[i]] > a[r[i]] ? l[i] : r[i]);
lo[0][i] = l[i] ^ r[i] ^ hi[0][i];
}
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i <= N_; ++i) {
hi[j][i] = hi[j - 1][hi[j - 1][i]];
lo[j][i] = lo[j - 1][lo[j - 1][i]];
}
}
for (int i = 1; i <= N_; ++i) {
id[a[i]] = i;
}
vector<int> ord(N_);
iota(ord.begin(), ord.end(), 1);
spa.build(ord, [&](int i, int j) {
return a[i] > a[j] ? i : j;
});
}
int go(int x, int y) {
int ret = 0;
for (int j = LOG - 1; j >= 0; --j) {
if (hi[j][x] && a[hi[j][x]] <= a[y]) {
x = hi[j][x];
ret += 1 << j;
}
}
for (int j = LOG - 1; j >= 0; --j) {
if (lo[j][x] && a[lo[j][x]] <= a[y]) {
x = lo[j][x];
ret += 1 << j;
}
}
return (x == y ? ret : -2);
}
int minimum_jumps(int A, int B, int C, int D) {
if (a[B + 1] > a[spa.get(C, D)]) {
return -1;
}
int ih = spa.get(B, C - 1);
int bl = A, br = B;
while (bl < br) {
int mid = (bl + br) / 2;
int cx = spa.get(mid, B);
if (a[cx] < a[ih]) {
br = mid;
} else {
bl = mid + 1;
}
}//bl is in H
int iabx = spa.get(bl, B);
if (iabx == ih) {
if (r[iabx] > C && r[iabx] <= D + 1) {
return 1;
} else {
return -1;
}
}
if (bl > A && r[bl] > C && r[bl] <= D + 1) {
return 1;
}
if (r[ih] > C && r[ih] <= D + 1) {
return go(iabx, ih) + 1;
} else {
return -1;
}
}
