#include "jumps.h"
#include <bits/stdc++.h>
using ll = long long;
using std::array;
using std::vector;
using std::pair;
constexpr int LOG = 18;
class range_max {
int size;
vector<int> data;
public:
range_max() = default;
explicit range_max(const vector<int>& v) {
size = (int)v.size();
data.resize(2 * size);
for (int i = 0; i < size; ++i) {
data[size + i] = v[i];
}
for (int i = size - 1; i > 0; --i) {
data[i] = std::max(data[2 * i], data[2 * i + 1]);
}
}
int fold(int l, int r) const {
l += size, r += size;
int ret = 0;
while (l < r) {
if (l & 1) ret = std::max(ret, data[l++]);
if (r & 1) ret = std::max(ret, data[--r]);
l >>= 1;
r >>= 1;
}
return ret;
}
};
vector<int> height;
range_max rmq;
array<vector<int>, LOG> left, right, high;
void init(int N, vector<int> H) {
height.reserve(N + 2);
height.push_back(N + 1);
for (const int x : H) {
height.push_back(x);
}
height.push_back(N + 1);
rmq = range_max(height);
N += 2;
for (int k = 0; k < LOG; ++k) {
left[k].resize(N);
right[k].resize(N);
high[k].resize(N);
}
vector<int> stack;
for (int i = 0; i < N; ++i) {
while (!stack.empty() and height[i] > height[stack.back()]) {
stack.pop_back();
}
left[0][i] = stack.empty() ? i : stack.back();
stack.push_back(i);
}
for (int i = N - 1; i >= 0; --i) {
while (!stack.empty() and height[i] > height[stack.back()]) {
stack.pop_back();
}
right[0][i] = stack.empty() ? i : stack.back();
stack.push_back(i);
}
for (int i = 0; i < N; ++i) {
high[0][i] = height[left[0][i]] > height[right[0][i]] ? left[0][i] : right[0][i];
}
for (int k = 0; k + 1 < LOG; ++k) {
for (int i = 0; i < N; ++i) {
left[k + 1][i] = left[k][left[k][i]];
right[k + 1][i] = right[k][right[k][i]];
high[k + 1][i] = high[k][high[k][i]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A += 1, B += 1, C += 1, D += 1;
const int goal_max = rmq.fold(C, D + 1);
if (rmq.fold(B, C) > goal_max) {
return -1;
}
int ans = 0, u = B;
for (int k = LOG - 1; k >= 0; --k) {
if (height[left[k][u]] < goal_max and A <= left[k][u]) {
ans += 1 << k;
u = left[k][u];
}
}
for (int k = LOG - 1; k >= 0; --k) {
if (height[high[k][u]] < goal_max) {
ans += 1 << k;
u = high[k][u];
}
}
if (u >= C) {
return ans;
}
for (int k = LOG - 1; k >= 0; --k) {
if (height[right[k][u]] < C) {
ans += 1 << k;
u = right[k][u];
}
}
return ans + 1;
}
