#include <bits/stdc++.h>
#include "jumps.h"
// #include "stub.cpp"
using namespace std;
const int lg = 20;
vector<int> h;
vector<vector<int>> sp, spl, spr;
void init(int n, vector<int> H) {
h = H;
stack<int> s;
spl.assign(n, vector<int>(lg, -1));
for (int i = 0; i < n; i++) {
while (!s.empty() && h[s.top()] < h[i]) s.pop();
spl[i][0] = (s.empty() ? -1 : s.top());
s.push(i);
}
while (!s.empty()) s.pop();
sp = spr = spl;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && h[i] > h[s.top()]) s.pop();
if (s.empty()) sp[i][0] = spl[i][0];
else {
spr[i][0] = s.top();
sp[i][0] = (spl[i][0] == -1 || h[spl[i][0]] < h[spr[i][0]] ? spr[i][0] : spl[i][0]);
}
s.push(i);
}
for (int i = 1; i < lg; i++) {
for (int j = 0; j < n; j++) {
if (sp[j][i - 1] != -1) sp[j][i] = sp[sp[j][i - 1]][i - 1];
if (spl[j][i - 1] != -1) spl[j][i] = spl[spl[j][i - 1]][i - 1];
if (spr[j][i - 1] != -1) spr[j][i] = spr[spr[j][i - 1]][i - 1];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
for (int i = lg - 1; i >= 0; i--) {
if (a <= spl[b][i] && h[spl[b][i]] < h[c]) b = spl[b][i];
}
int cnt = 0;
for (int i = lg - 1; i >= 0; i--) {
if (sp[b][i] != -1 && h[sp[b][i]] < h[c]) {
cnt += (1 << i);
b = sp[b][i];
}
}
for (int i = lg - 1; i >= 0; i--) {
if (spr[b][i] != -1 && h[spr[b][i]] < h[c]) {
cnt += (1 << i);
b = spr[b][i];
}
}
return (spr[b][0] == c ? cnt + 1 : -1);
}
