#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
int B[N][18];
int L[N][18];
int R[N][18];
void init(int n, vector<int> H) {
L[n][0] = R[n][0] = n;
H.push_back(1e9 + 10);
vector<int> stack;
for (int i = 0; i < n; i++) {
while (!stack.empty() && H[stack.back()] < H[i])
stack.pop_back();
L[i][0] = (stack.empty() ? n : stack.back());
stack.push_back(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.empty() && H[stack.back()] < H[i])
stack.pop_back();
R[i][0] = (stack.empty() ? n : stack.back());
stack.push_back(i);
}
stack.clear();
for (int i = 0; i <= n; i++) {
B[i][0] = (H[L[i][0]] < H[R[i][0]] ? R[i][0] : L[i][0]);
}
// for (int i = 0; i < n; i++)
// cout << L[i][0] << ' ';
// cout << '\n';
// for (int i = 0; i < n; i++)
// cout << R[i][0] << ' ';
// cout << '\n';
// cout << '\n';
for (int k = 1; k < 18; k++) {
for (int i = 0; i <= n; i++) {
L[i][k] = L[L[i][k - 1]][k - 1];
R[i][k] = R[R[i][k - 1]][k - 1];
B[i][k] = B[B[i][k - 1]][k - 1];
}
}
}
int minimum_jumps(int l, int r, int c, int d) {
int ans = 0;
for (int k = 17; k >= 0; k--) {
if (L[r][k] >= l && R[L[r][k]][0] <= d)
r = L[r][k];
}
for (int k = 17; k >= 0; k--) {
if (r < c && R[B[r][k]][0] <= d) {
r = B[r][k];
ans += (1 << k);
}
}
for (int k = 17; k >= 0; k--) {
if (r < c && R[r][k] <= d) {
r = R[r][k];
ans += (1 << k);
}
}
if (c <= r && r <= d) return ans;
return -1;
}
