#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int LG = 18;
int n, sp[N][LG], h[N], pos[N], las[N], nex[N], nxt[N][LG], nxt2[N][LG], lg[N];
int query(int x, int y) {
int j = lg[y - x + 1];
return max(sp[x][j], sp[y - (1 << j) + 1][j]);
}
void init(int _n, std::vector<int> _h) {
n = _n;
for (int i = 0; i < _n; i++) {
h[i + 1] = _h[i];
sp[i + 1][0] = h[i + 1];
}
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; i++) pos[h[i]] = i;
for (int i = 1; i < LG; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
sp[j][i] = max(sp[j][i - 1], sp[j + (1 << (i - 1))][i - 1]);
}
}
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && h[st.top()] < h[i]) st.pop();
if (!st.empty()) las[i] = h[st.top()];
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && h[st.top()] < h[i]) st.pop();
if (!st.empty()) nex[i] = h[st.top()];
st.push(i);
}
for (int i = 1; i <= n; i++) {
nxt[h[i]][0] = max(las[i], nex[i]);
// cout << "nxt: " << i << " " << nxt[i][0] << '\n';
if (!nxt[h[i]][0]) nxt[h[i]][0] = n + 1;
if (!las[i] && !nex[i]) nxt2[h[i]][0] = n + 1;
else if (!las[i]) nxt2[h[i]][0] = nex[i];
else if (!nex[i]) nxt2[h[i]][0] = las[i];
else nxt2[h[i]][0] = min(las[i], nex[i]);
}
nxt[n + 1][0] = nxt2[n + 1][0] = n + 1;
for (int j = 1; j < LG; j++) {
for (int i = 1; i <= n + 1; i++) {
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
nxt2[i][j] = nxt2[nxt2[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
int right_max = query(C, D);
int lo = A, hi = B;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (query(mid, C-1) <= right_max) hi = mid;
else lo = mid + 1;
}
if (query(lo, C-1) > right_max) return -1;
int obs = query(lo, C-1);
int cur = query(lo, B), res = 0;
for (int i = LG - 1; i >= 0; i--) {
if (nxt[cur][i] < obs) {
cur = nxt[cur][i];
res += (1 << i);
}
}
if (nxt[cur][0] >= obs && nxt[cur][0] <= right_max) {
if (C <= pos[nxt[cur][0]] && pos[nxt[cur][0]] <= D) return res + 1;
return res + 2;
}
for (int i = LG - 1; i >= 0; i--) {
if (pos[nxt2[cur][i]] < C) {
cur = nxt2[cur][i];
res += (1 << i);
}
}
if (nxt2[cur][0] >= C) return res + 1;
return -1;
}
