#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9 + 67;
const int MAXN = 2e5 + 5;
const int MAXLOG = 19;
int N;
vector<int> H, tree;
vector<vector<int>> jR, jM;
int res;
int ret(int l, int r) {
if (min(l, r) == -1) return max(l, r);
return (H[l] > H[r] ? l : r);
}
void build(int tl = 0, int tr = N-1, int i = 1) {
if (tl == tr) {
tree[i] = tl;
return ;
}
int tm = (tl + tr) / 2;
build(tl, tm, i * 2);
build(tm + 1, tr, i * 2 + 1);
tree[i] = ret(tree[i * 2], tree[i * 2 + 1]);
}
int query(int l, int r, int tl = 0, int tr = N-1, int i = 1) {
if (l > r) return -1;
if (tl == l && tr == r) return tree[i];
int tm = (tl + tr) / 2;
return ret(query(l, min(r, tm), tl, tm, i * 2), query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1));
}
void init(int N, vector<int> H) {
::N = N, ::H = H;
tree.resize(N*4), jR.resize(MAXLOG, vector<int>(N)), jM.resize(MAXLOG, vector<int>(N));
vector<int> stk;
for(int i = N-1; i >= 0; i--) {
while(stk.size() && H[stk.back()] < H[i]) stk.pop_back();
jM[0][i] = (stk.size() ? stk.back() : i);
jR[0][i] = (stk.size() ? stk.back() : i);
stk.push_back(i);
}
while(stk.size()) stk.pop_back();
for(int i = 0; i < N; i++) {
while(stk.size() && H[stk.back()] < H[i]) stk.pop_back();
jM[0][i] = (stk.size() ? max(jM[0][i], stk.back()) : jM[0][i]);
stk.push_back(i);
}
for(int j = 1; j < MAXLOG; j++) {
for(int i = 0; i < N; i++) {
jM[j][i] = jM[j-1][jM[j-1][i]];
jR[j][i] = jR[j-1][jR[j-1][i]];
}
}
build();
}
int find(int A, int B, int X) { // leftmoost i such that H[max{i, B}] < H[E]
int l = A, r = B+1;
while(l < r) {
int m = (l + r) / 2;
if (H[query(m, B)] < H[X]) r = m;
else l = m + 1;
}
return l;
}
int lift(vector<vector<int>> &jump, int S, int E) {
int j = MAXLOG - 1;
while(j >= 0) {
if (H[jump[j][S]] < H[E]) {
S = jump[j][S];
res += (1 << j);
}
j--;
}
return S;
}
int minimum_jumps(int A, int B, int C, int D) {
res = 0;
int E = query(C, D), T = query(B, C);
if (T > E) return -1;
int S = query(find(A, B, E), B);
if (S == -1) return -1;
int ret = jR[0][lift(jR, lift(jM, S, E), E)];
return (C <= ret && ret <= D) ? res+1 : -1;
}
