#include "jumps.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int MxN = 2e5 + 5, K = 19;
int n, l[MxN], r[MxN], dp[K][MxN], dp2[K][MxN];
vector<int> h;
void init(int N, std::vector<int> H) {
n = N; h = H;
stack<int> st;
for (int i = 0; i < n; i++) {
l[i] = -1;
while (!st.empty() && h[i] > h[st.top()]) st.pop();
if (!st.empty()) l[i] = st.top();
st.emplace(i);
}
for (int i = 0; i < n; i++) dp[0][i] = (~l[i] ? l[i] : i);
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
r[i] = -1;
while (!st.empty() && h[i] > h[st.top()]) st.pop();
if (!st.empty()) r[i] = st.top();
st.emplace(i);
}
for (int i = 0; i < n; i++) dp2[0][i] = (~r[i] ? r[i] : i);
for (int i = 1; i < K; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
dp2[i][j] = dp2[i - 1][dp2[i - 1][j]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0;
int st = A, ed = C;
while (1) {
int cst = st;
for (int i = K - 1; i >= 0; i--) {
if (h[dp2[i][st]] < h[ed]) st = dp2[i][st], ans += (1 << i);
}
if (dp2[0][st] == ed) {ans++; break;}
for (int i = K - 1; i >= 0 ; i--) {
if (h[dp[i][st]] < h[ed]) st = dp[i][st], ans += (1 << i);
}
if (dp[0][st] == ed) {ans++; break;}
if (cst == st) return -1;
}
return ans;
}
