#include "jumps.h"
#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int n, h[maxn], pre[maxn], nex[maxn];
int f[20][maxn];
int jp[20][maxn], gojo[20][maxn];
ii orz[20][maxn];
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; i++) h[i] = H[i-1];
h[0] = h[n+1] = INT_MAX;
for (int i = 1; i <= n; i++) {
int k = i-1;
while (h[k] < h[i]) k = pre[k];
pre[i] = k;
}
for (int i = n; i >= 1; i--) {
int k = i+1;
while (h[k] < h[i]) k = nex[k];
nex[i] = k;
}
for (int i = 1; i <= n; i++) {
jp[0][i] = pre[i];
gojo[0][i] = nex[i];
}
gojo[0][n+1] = n+1;
for (int i = 1; i <= n; i++) orz[0][i] = ii{h[i], i};
for (int i = 1; (1<<i) <= n; i++)
for (int j = 1; j + (1<<i) - 1 <= n; j++) orz[i][j] = max(orz[i-1][j], orz[i-1][j+(1<<(i-1))]);
for (int i = 1; i <= n; i++) {
if (pre[i] > 0 && nex[i] <= n) {
f[0][i] = (h[pre[i]] > h[nex[i]] ? pre[i] : nex[i]);
continue;
}
if (pre[i] > 0) {
f[0][i] = pre[i];
continue;
}
if (nex[i] <= n) {
f[0][i] = nex[i];
continue;
}
f[0][i] = n+1;
}
f[0][n+1] = n+1;
for (int i = 1; i < 20; i++) for (int j = 1; j <= n+1; j++) f[i][j] = f[i-1][f[i-1][j]];
for (int i = 1; i < 20; i++) {
for (int j = 0; j <= n; j++) jp[i][j] = jp[i-1][jp[i-1][j]];
for (int j = 1; j <= n+1;j++)gojo[i][j] = gojo[i-1][gojo[i-1][j]];
}
}
ii get_max(int u, int v) {
int k = __lg(v-u+1);
return max(orz[k][u], orz[k][v-(1<<k)+1]);
}
int kc[maxn];
int minimum_jumps(int A, int B, int C, int D) {
++A; ++B; ++C; ++D;
ii m = get_max(B, C-1), m2 = get_max(C, D);
if (m.fi > m2.fi) return -1;
int lo = A-1, hi = B;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (get_max(mid, B).fi < m2.fi) hi = mid;
else lo = mid;
}
A = get_max(hi, B).se;
if (nex[A] >= C) {
A = nex[A];
return 1;
}
int ans = 0;
for (int i = 19; i >= 0; i--){
if (h[f[i][A]] <= m.fi) {
ans += (1<<i);
A = f[i][A];
}
}
if (A != m.se) {
if (h[f[0][A]] <= m2.fi) {
A = f[0][A];
++ans;
}
}
if (A < C) {
++ans;
A = nex[A];
}
return (C <= A and A <= D ? ans : -1);
}
