#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 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));
build();
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();
if (stk.size() && H[stk.back()] > H[jM[0][i]]) jM[0][i] = stk.back();
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]];
}
}
}
int find(int A, int B, int X) { // leftmost 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 liftright(int S, int C, int D) {
int res = 0, j = MAXLOG - 1;
while(j >= 0) {
if (jR[j][S] < C) {
S = jR[j][S];
res += (1 << j);
}
j--;
}
return (C <= jR[0][S] && jR[0][S] <= D ? res+1 : INF);
}
int minimum_jumps(int A, int B, int C, int D) {
int E = query(C, D), T = query(B, C);
int le = find(A, B, E); if (le == B+1) return -1;
int S = query(le, B); if (S == -1) return -1;
int res = 0, j = MAXLOG - 1;
while(j >= 0) {
if (H[jM[j][S]] < H[T]){
S = jM[j][S];
res += (1 << j);
}
j--;
}
if (C <= S && S <= D) return res;
res += min(liftright(S, C, D), 1 + liftright(jM[0][S], C, D));
return res < INF ? res : -1;
}
