#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
const int lg = 20;
int a[mxN], righ[mxN][lg], lef[mxN][lg], best[mxN][lg];
void init(int N, vector<int> H) {
for (int i = 1; i <= N; i++) a[i] = H[i - 1];
stack<int> st;
for (int i = 1; i <= N; i++) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (st.empty()) lef[i][0] = i;
else lef[i][0] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = N; i >= 1; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (st.empty()) righ[i][0] = i;
else righ[i][0] = st.top();
st.push(i);
}
for (int i = 1; i <= N; i++) {
if (a[righ[i][0]] > a[lef[i][0]]) best[i][0] = righ[i][0];
else best[i][0] = lef[i][0];
}
for (int j = 1; j < lg; j++) {
for (int i = 1; i <= N; i++) {
best[i][j] = best[best[i][j - 1]][j - 1];
righ[i][j] = righ[righ[i][j - 1]][j - 1];
lef[i][j] = lef[lef[i][j - 1]][j - 1];
}
}
}
int get_max(int l, int r, int v) {
if (a[r] > v) return -1;
for (int j = lg - 1; j >= 0; j--) {
if (lef[r][j] >= l && a[lef[r][j]] < v) r = lef[r][j];
}
return r;
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
// top in each intervals [A..B], [B+1..C-1], [C..D]
int midx = get_max(C, D, 1e9);
int start = get_max(A, B, a[midx]);
if (start == -1) return -1;
if (B == C - 1) return 1;
int barrier = a[get_max(B + 1, C - 1, 1e9)];
if (barrier < a[start]) return 1;
if (barrier > a[midx]) return -1;
// climb until barrier using skip-edge aka. high-edge
int ans = 0;
for (int j = lg - 1; j >= 0; j--) {
if (a[best[start][j]] <= barrier) start = best[start][j], ans += (1 << j);
}
// end up at barrier
if (a[start] == barrier) return ans + 1;
// jump over barrier
if (a[best[start][0]] < a[midx]) return ans + 2;
// if not jump over, the must move to right to [C..D]
for (int j = lg - 1; j >= 0; j--) {
if (righ[start][j] < C) start = righ[start][j], ans += (1 << j);
}
return ans + 1;
}
