#include "jumps.h"
#include <bits/stdc++.h>
#define emb emplace_back
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
const int LG = 18;
int n, a[N], l[N], r[N];
vector <int> adj[N], mx[N], mn[N];
int parmx[N][LG], parmn[N][LG];
void dfsmx(int u, int p){
if (u != p) parmx[u][0] = p;
for (auto v : mx[u]) {
if (v == p) continue;
cout << u << " -> " << v << "\n";
dfsmx(v, u);
}
}
void dfsmn(int u, int p){
if (u != p) parmn[u][0] = p;
for (auto v : mn[u]) {
if (v == p) continue;
dfsmn(v, u);
}
}
void build(int u, int p){
for (int i = 1; i < LG; i++) {
for (int j = 1; j <= n; j++) {
parmx[j][i] = parmx[parmx[j][i - 1]][i - 1];
parmn[j][i] = parmn[parmn[j][i - 1]][i - 1];
}
}
}
void init(int nn, std::vector<int> h) {
n = nn;
for (int i = 0; i < n; i++) a[i + 1] = h[i];
stack <pii> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && st.top().first < a[i]) st.pop();
if (!st.empty()) l[i] = st.top().second;
st.emplace(a[i], i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && st.top().first < a[i]) st.pop();
if (!st.empty()) r[i] = st.top().second;
st.emplace(a[i], i);
}
while (!st.empty()) st.pop();
for (int i = 1; i <= n; i++) {
if (l[i]) adj[i].emb(l[i]);
if (r[i]) adj[i].emb(r[i]);
// cout << i << " : ";
// if (l[i]) cout << l[i] << " ";
// if (r[i]) cout << r[i] << " ";
// cout << "\n";
// cout << (a[l[i]] > a[r[i]] ? l[i] : r[i]) << " -> " << i << "\n";
if (a[l[i]] > a[r[i]]) {
if (l[i]) mx[l[i]].emb(i);
if (r[i]) mn[r[i]].emb(i);
}
else {
if (r[i]) mx[l[i]].emb(i);
if (l[i]) mn[r[i]].emb(i);
}
}
a[0] = inf;
pii mxnode = {0, 0};
for (int i = 1; i <= n; i++) {
// cout << i << " : ";
// for (auto e : mx[i]) cout << e << " ";
// cout << "\n";
mxnode = max(mxnode, {a[i], i});
}
dfsmx(mxnode.second, mxnode.second);
dfsmn(mxnode.second, mxnode.second);
build(mxnode.second, mxnode.second);
// for (int i = 1; i <= n; i++) {
// cout << i << " : ";
// for (int j = 0; j <= 3; j++) cout << parmx[i][j] << " ";
// cout << "\n";
// }
}
int minimum_jumps(int l1, int r1, int l2, int r2) {
l1++, r1++, l2++, r2++;
int u = l1, v = l2;
int ans = 0;
for (int i = LG - 1; i >= 0; i--) {
if (a[parmx[u][i]] <= a[v]) u = parmx[u][i], ans += (1 << i);
if (u == v) return ans;
}
for (int i = LG - 1; i >= 0; i--) {
if (a[parmn[u][i]] <= a[v]) u = parmn[u][i], ans += (1 << i);
if (u == v) return ans;
}
return -1;
}
