#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "D:\\debug.h"
#else
#define debug(...)
#endif
namespace {
const int maxn = 2e5 + 5;
const int LG = 18;
int n;
int h[maxn];
int sl[maxn][LG + 1], sr[maxn][LG + 1];
int nxt[maxn][LG + 1];
}
void init(int N, std::vector<int> H) {
n = N;
for (int i = 1; i <= n; ++i) {
h[i] = H[i - 1];
}
stack<int> st;
for (int i = 1; i <= n; ++i) {
while (!st.empty() and h[st.top()] < h[i]) {
st.pop();
}
sl[i][0] = st.empty() ? 0 : st.top();
st.push(i);
}
st = stack<int>();
for (int i = n; i; --i) {
while (!st.empty() and h[st.top()] < h[i]) {
st.pop();
}
sr[i][0] = st.empty() ? 0 : st.top();
st.push(i);
}
for (int i = 1; i <= n; ++i) {
nxt[i][0] = (sr[i][0] == 0 || h[sr[i][0]] < h[sl[i][0]] ? sl[i][0] : sr[i][0]);
}
for (int j = 1; j <= LG; ++j) {
for (int i = 1; i <= n + 1; ++i) {
sl[i][j] = sl[sl[i][j - 1]][j - 1];
sr[i][j] = sr[sr[i][j - 1]][j - 1];
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
}
}
int get(int l, int r) {
if (l > r) return 0;
int cur = l;
for (int i = LG; i >= 0; --i) {
if (sr[cur][i] and sr[cur][i] <= r) {
cur = sr[cur][i];
}
}
return cur;
}
int minimum_jumps(int A, int B, int C, int D) {
int a = A + 1, b = B + 1, c = C + 1, d = D + 1;
int m = h[get(c, d)];
int mx = h[get(b + 1, c - 1)];
int opt = b;
for (int i = LG; i >= 0; --i) {
if (sl[opt][i] >= a and h[sl[opt][i]] < m) {
opt = sl[opt][i];
}
}
int en = b;
for (int i = LG; i >= 0; --i) {
if (sr[en][i] and sr[en][i] < c) {
en = sr[en][i];
}
}
en = sr[en][0];
if (en > d) {
return -1;
}
int res = 0;
for (int i = LG; i >= 0; --i) {
if (nxt[opt][i] and h[nxt[opt][i]] < h[en]) {
res += (1 << i);
opt = nxt[opt][i];
}
}
if (sr[opt][0] >= c and sr[opt][0] <= d) {
return res + 1;
}
if (sl[opt][0] and sr[sl[opt][0]][0] >= c and sr[sl[opt][0]][0] <= d) {
return res + 2;
}
for (int i = LG; i >= 0; --i) {
if (sr[opt][i] and sr[opt][i] < c) {
res += (1 << i);
opt = sr[opt][i];
}
}
if (sr[opt][0] >= c and sr[opt][0] <= d) {
return res + 1;
}
return -1;
}
