#include "jumps.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int LOG = 21;
const int N = 2e5 + 5;
int h[N];
int sp[N][LOG];
int spl[N][LOG];
int spr[N][LOG];
void init(int N, vector<int> H) {
int n = N;
for (int i = 1; i <= n; ++ i) {
h[i] = H[i - 1];
for (int j = LOG - 1; ~j; -- j) {
sp[i][j] = spl[i][j] = spr[i][j] = -1;
}
}
stack<int> st;
for (int i = 1; i <= n; ++ i) {
while (!st.empty() and h[st.top()] < h[i]) st.pop();
if (!st.empty()) {
spl[i][0] = st.top();
}
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n; i; -- i) {
while (!st.empty() and h[st.top()] < h[i]) st.pop();
if (!st.empty()) {
spr[i][0] = st.top();
if (spl[i][0] == -1 or h[spl[i][0]] < h[spr[i][0]]) sp[i][0] = spr[i][0];
else sp[i][0] = spl[i][0];
}
else sp[i][0] = spl[i][0];
st.push(i);
}
for (int j = 1; j < LOG; ++ j) {
for (int i = 1; i <= n; ++ i) {
if (~sp[i][j - 1]) sp[i][j] = sp[sp[i][j - 1]][j - 1];
if (~spl[i][j - 1]) spl[i][j] = spl[spl[i][j - 1]][j - 1];
if (~spr[i][j - 1]) spr[i][j] = spr[spr[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
a += 1, b += 1, c += 1, d += 1;
int x = b;
int ans = 0;
for (int j = LOG - 1; ~j; -- j) {
if (spl[x][j] >= a and h[spl[x][j]] < h[d]) {
x = spl[x][j];
}
}
for (int j = LOG - 1; ~j; -- j) {
if (~sp[x][j] and h[sp[x][j]] < h[d]) {
ans += 1 << j;
x = sp[x][j];
}
}
for (int j = LOG - 1; ~j; -- j) {
if (~spr[x][j] and h[spr[x][j]] < h[d]) {
ans += 1 << j;
x = spr[x][j];
}
}
return (spr[x][0] == d ? ans + 1 : -1);
return 0;
}
