#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int i, n, x;
stack<pair<int, int> > S;
vector<int> adj[200005];
int pos[200005][2];
int rmv[200005];
int h[200005];
int up[200005][22];
int val[200005][22];
void dfs(int x) {
for (int k=2; k <= 21; ++k) up[x][k] = up[up[x][k-1]][k-1];
if (x != 0) val[x][0] = pos[x][1]-pos[x][0];
for (int k=1; k <= 21; ++k) val[x][k] = min(val[x][k-1], val[up[x][k-1]][k-1]);
for (auto y : adj[x]) dfs(y);
}
void init(int N, vector<int> H) {
n = N;
for (i=1; i <= n; ++i) h[i] = H[i-1];
for (i=1; i <= n; ++i) rmv[i] = -1;
while (!S.empty()) S.pop();
S.push(make_pair(INT_MAX, 0));
up[0][0] = 0;
up[0][1] = 0;
val[0][0] = INT_MAX;
for (i=1; i <= n; ++i) {
up[i][0] = i;
while (!S.empty() && S.top().X < h[i]) S.pop();
adj[S.top().Y].push_back(i);
up[i][1] = S.top().Y;
S.push(make_pair(h[i], i));
pos[i][0] = (int)S.size()-1;
}
while (!S.empty()) S.pop();
S.push(make_pair(INT_MAX, 0));
for (i=n; i >= 1; --i) {
while (!S.empty() && S.top().X < h[i]) {
rmv[S.top().Y] = i;
S.pop();
}
S.push(make_pair(h[i], i));
pos[i][1] = (int)S.size()-1;
}
dfs(0);
}
int minimum_jumps(int A, int B, int C, int D) {
++A;
++B;
++C;
++D;
int ans = INT_MAX;
if (A <= rmv[C]) return -1;
for (int k=21; k >= 0; --k) {
if (up[A][k] > rmv[C]) {
ans = min(ans, val[A][k]);
A = up[A][k];
}
}
return (ans == INT_MAX) ? -1 : (pos[B][0]+ans-pos[C][1]);
}
