#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int MxN = 2e5 + 5, K = 19;
int n, rt, t, h[MxN], l[MxN], r[MxN], tin[MxN], tout[MxN], dep[MxN], dp[K][MxN];
void dfs (int cur, int par) {
tin[cur] = ++t; dep[cur] = dep[par] + 1; dp[0][cur] = par;
if (l[cur]) dfs(l[cur], cur);
if (r[cur]) dfs(r[cur], cur);
tout[cur] = t;
}
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 = 0; i < n; i++) l[i] = r[i] = -1;
for (int i = 1; i <= n; i++) {
while (!st.empty() && h[i] > h[st.top()]) l[i] = st.top(), st.pop();
if (!st.empty()) r[st.top()] = i;
else rt = i;
st.emplace(i);
}
dfs(rt, 0);
for (int i = 1; i < K; i++) {
for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0;
int st = A + 1, ed = C + 1;
if (tin[ed] > tin[st] || tout[st] > tout[ed]) return -1;
for (int i = K - 1; i >= 0; i--) {
if (dep[dp[i][st]] >= dep[ed]) st = dp[i][st], ans++;
}
ans += dep[st] - dep[ed];
return ans;
}
