#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 10, LOG = 18;
vector<int> g[mxn], rg[mxn];
vector<int> H;
int N;
int high[mxn][LOG], low[mxn][LOG];
bool visited[mxn];
void dfs(int cur, int par) {
if (visited[cur]) return;
visited[cur] = 1;
low[cur][0] = g[cur][0];
high[cur][0] = g[cur][1];
for (int i = 1; i < LOG; i++) {
low[cur][i] = low[low[cur][i - 1]][i - 1];
high[cur][i] = high[high[cur][i - 1]][i - 1];
}
for (auto x : rg[cur]) dfs(x, cur);
}
void init(int _N, vector<int> _H) {
N = _N, H = _H;
int mx = 0, pos = 0;
for (int i = 0; i < N; i++) {
if (H[i] > mx) {
mx = H[i];
pos = i;
}
}
H.push_back(1e9);
stack<int> s;
s.push(0);
for (int i = 1; i < N; i++) {
while (s.size() && H[i] > H[s.top()]) s.pop();
if (s.size()) g[i].push_back(s.top());
s.push(i);
}
while (s.size()) s.pop();
s.push(N - 1);
for (int i = N - 2; i >= 0; i--) {
while (s.size() && H[i] > H[s.top()]) s.pop();
if (s.size()) g[i].push_back(s.top());
s.push(i);
}
for (int i = 0; i < N; i++) {
for (auto x : g[i]) rg[x].push_back(i);
if (g[i].size() == 2 && H[g[i][0]] > H[g[i][1]]) swap(g[i][0], g[i][1]);
while (g[i].size() < 2) g[i].push_back(N);
}
dfs(pos, pos);
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0;
for (int i = LOG - 1; i >= 0; i--) {
if (H[high[A][i]] <= H[C]) {
A = high[A][i];
ans += 1 << i;
}
}
for (int i = LOG - 1; i >= 0; i--) {
if (H[low[A][i]] <= H[C]) {
A = low[A][i];
ans += 1 << i;
}
}
return (H[A] == H[C] ? ans : -1);
}
