#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];
int curr[200005];
void dfs(int x) {
for (int k=1; k <= 21; ++k) up[x][k] = up[up[x][k-1]][k-1];
if (x != 0) {
curr[x] = pos[x][1]-pos[x][0];
if (up[x][0] != 0) val[x][0] = min(curr[x], curr[up[x][0]]);
else val[x][0] = curr[x];
}
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;
for (i=0; i <= N; ++i) adj[i].clear();
up[0][0] = 0;
curr[0] = INT_MAX;
for (int k=0; k <= 21; ++k) val[0][k] = INT_MAX;
while (!S.empty()) S.pop();
S.push(make_pair(INT_MAX, 0));
for (i=1; i <= n; ++i) {
while (!S.empty() && S.top().X < h[i]) S.pop();
adj[S.top().Y].push_back(i);
up[i][0] = 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;
if (A <= rmv[C]) return -1;
int ans = pos[B][1]-pos[B][0];
for (int k=21; k >= 0; --k) {
if (up[A][k] > 0 && up[A][k] > rmv[C]) {
ans = min(ans, val[A][k]);
A = up[A][k];
}
}
return pos[B][0]+ans-pos[C][1];
}
