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