#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'000 + 10,
MAX = 1'000'000,
LG = 17;
int n;
int h[MAXN];
namespace ST {
int st[MAXN][LG + 1];
void init() {
for (int i = 0; i < n; ++i) st[i][0] = i;
for (int j = 1; j <= LG; ++j) {
for (int i = 0; i <= (n - 1) - (1 << j) + 1; ++i) {
int lt = st[i][j - 1], rt = st[i + (1 << (j - 1))][j - 1];
st[i][j] = (h[lt] > h[rt] ? lt : rt);
}
}
}
int get(int l, int r) {
int j = __lg(r - l + 1);
int lt = st[l][j], rt = st[r - (1 << j) + 1][j];
return h[lt] > h[rt] ? lt : rt;
}
}
int goL[MAXN], goR[MAXN];
int up[MAXN][LG + 1], upR[MAXN][LG + 1];
void init(int N, std::vector<int> H) {
n = N;
for (int i = 0; i < n; ++i) h[i] = H[i];
{ // go left
stack<int> st;
for (int i = 0; i < n; ++i) {
while (st.size() && h[st.top()] < h[i]) st.pop();
goL[i] = (st.size() ? st.top() : n);
st.push(i);
}
}
{ // go right
stack<int> st;
for (int i = n - 1; i >= 0; --i) {
while (st.size() && h[st.top()] < h[i]) st.pop();
goR[i] = (st.size() ? st.top() : n);
st.push(i);
}
}
h[n] = -1;
fill(up[n], up[n] + LG + 1, n);
for (int i = 0; i < n; ++i) {
up[i][0] = (h[goR[i]] > h[goL[i]] ? goR[i] : goL[i]);
}
h[n] = MAX;
fill(upR[n], upR[n] + LG + 1, n);
for (int i = 0; i < n; ++i) {
upR[i][0] = (h[goR[i]] < h[goL[i]] ? goR[i] : goL[i]);
}
for (int j = 1; j <= LG; ++j) {
for (int i = 0; i < n; ++i) {
up[i][j] = up[up[i][j - 1]][j - 1];
upR[i][j] = upR[upR[i][j - 1]][j - 1];
}
}
ST::init();
}
int minimum_jumps(int A, int B, int C, int D) {
int ret = 0;
int X = ST::get(B, D);
{ // bin search
int le = A, ri = B, it = B;
while (le <= ri) {
int mid = (le + ri) >> 1;
if (h[ST::get(mid, B)] <= h[X]) ri = mid - 1, it = mid;
else le = mid + 1;
}
A = ST::get(it, B);
}
int Y = ST::get(B, C - 1);
for (int j = LG; j >= 0; --j) {
if (h[up[A][j]] <= h[Y]) {
ret += (1 << j);
A = up[A][j];
}
}
if (A < h[Y] && h[up[A][0]] <= h[X]) {
A = up[A][0];
ret += 1;
}
for (int j = LG; j >= 0; --j) {
if (h[upR[A][j]] <= h[Y]) {
ret += (1 << j);
A = upR[A][j];
}
}
if (C <= A && A <= D) return ret;
ret += 1;
A = goR[A];
if (C <= A && A <= D) return ret;
return -1;
}
