#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int lg = 20, MAXN = 2e5 + 55;
int up[lg][MAXN][3], N, H[MAXN];
void init(int n, vector<int> h) {
N = n;
H[0] = H[N + 1] = 1e9 + 7;
for (int i = 1;i <= N;i ++) H[i] = h[i - 1];
N += 2;
stack<int> st;
for (int i = 0; i < N; ++i) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
if (st.size() > 0) up[0][i][0] = st.top();
else up[0][i][0] = i;
st.push(i);
} while (!st.empty()) st.pop();
for (int i = N - 1; i >= 0; --i) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
if (st.size() > 0) up[0][i][1] = st.top();
else up[0][i][1] = i;
st.push(i);
}
for (int i = 0; i < N; ++i) {
up[0][i][2] = H[up[0][i][0]] > H[up[0][i][1]] ? up[0][i][0] : up[0][i][1];
}
for (int bt = 1;bt < lg;bt ++) {
for (int i = 0;i < N;i ++) {
up[bt][i][0] = up[bt - 1][up[bt - 1][i][0]][0];
up[bt][i][1] = up[bt - 1][up[bt - 1][i][1]][1];
up[bt][i][2] = up[bt - 1][up[bt - 1][i][2]][2];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A ++; B ++; C ++; D ++;
for (int bt = lg - 1;bt >= 0;bt --) {
if (A <= up[bt][B][0] && H[up[bt][B][0]] < H[D]) {
B = up[bt][B][0];
}
}
int res = 1e9 + 7;
for (int ind = C;ind <= D;ind ++) {
int _B = B;
int cnt = 0;
for (int bt = lg - 1;bt >= 0;bt --) {
if (H[up[bt][B][2]] <= H[ind]) {
B = up[bt][B][2];
cnt += (1 << bt);
}
}
if (H[up[0][B][0]] > H[ind]) {
for (int bt = lg - 1;bt >= 0;bt --) {
if (H[up[bt][B][1]] <= H[ind]) {
B = up[bt][B][1];
cnt += (1 << bt);
}
}
} else {
for (int bt = lg - 1;bt >= 0;bt --) {
if (H[up[bt][B][0]] <= H[ind]) {
B = up[bt][B][0];
cnt += (1 << bt);
}
}
}
if (ind == B) {
res = min(res, cnt);
}
B = _B;
}
if (res == 1e9 + 7) return -1;
return res;
}
