#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 200000 + 5;
static const int LG = 19;
int N;
int H[MAXN];
int Lv[MAXN], Rv[MAXN];
int upHigh[MAXN][LG];
int upR[MAXN][LG];
int idxOfHeight[MAXN];
int lg2[MAXN];
int stMax[MAXN][LG];
int rangeMax(int l, int r) {
if (l > r)
return 0;
int j = lg2[r - l + 1];
return max(stMax[l][j], stMax[r - (1 << j) + 1][j]);
}
void init(int n, vector<int> h) {
N = n;
for (int i = 0; i < N; i++)
H[i] = h[i];
for (int i = 0; i < N; i++) {
Lv[i] = -1;
Rv[i] = -1;
}
vector<int> st;
st.reserve(N);
for (int i = 0; i < N; i++) {
while (!st.empty() && H[st.back()] < H[i]) {
Rv[st.back()] = i;
st.pop_back();
}
if (!st.empty())
Lv[i] = st.back();
st.push_back(i);
}
for (int i = 0; i < N; i++) {
int L = Lv[i], R = Rv[i];
if (L == -1)
upHigh[i][0] = R;
else if (R == -1)
upHigh[i][0] = L;
else
upHigh[i][0] = (H[L] > H[R]) ? L : R;
upR[i][0] = R;
}
for (int j = 1; j < LG; j++) {
for (int i = 0; i < N; i++) {
int p = upHigh[i][j - 1];
upHigh[i][j] = (p == -1) ? -1 : upHigh[p][j - 1];
p = upR[i][j - 1];
upR[i][j] = (p == -1) ? -1 : upR[p][j - 1];
}
}
for (int i = 0; i < N; i++)
idxOfHeight[H[i]] = i;
lg2[1] = 0;
for (int i = 2; i <= N; i++)
lg2[i] = lg2[i / 2] + 1;
for (int i = 0; i < N; i++)
stMax[i][0] = H[i];
for (int j = 1; j < LG; j++)
for (int i = 0; i + (1 << j) <= N; i++)
stMax[i][j] = max(stMax[i][j - 1], stMax[i + (1 << (j - 1))][j - 1]);
}
int minimum_jumps(int A, int B, int C, int D) {
int X = rangeMax(B, C - 1);
int Y = rangeMax(C, D);
if (X > Y)
return -1;
int l = A, r = B;
int bestH = 0;
while (l <= r) {
int mid = (l + r) >> 1;
int mx = rangeMax(mid, B);
if (mx < Y) {
bestH = mx;
r = mid - 1;
} else {
l = mid + 1;
}
}
int u = idxOfHeight[bestH];
int answer = 0;
for (int j = LG - 1; j >= 0; j--) {
int v = upHigh[u][j];
if (v != -1 && H[v] < X) {
u = v;
answer += 1 << j;
}
}
if (upR[u][0] != -1 && upR[u][0] >= C)
return answer + 1;
if (upHigh[u][0] != -1 && H[upHigh[u][0]] < Y)
return answer + 2;
for (int j = LG - 1; j >= 0; j--) {
int v = upR[u][j];
if (v != -1 && v < C) {
u = v;
answer += 1 << j;
}
}
return answer + 1;
}
