#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], jumpleft[N][LG];
void dfsmx(int u, int p){
// cout << "DFSMX\n";
if (u != p) parmx[u][0] = p;
for (auto v : mx[u]) {
// cout << u << " -> " << v << "\n";
if (v == p) continue;
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];
jumpleft[j][i] = jumpleft[jumpleft[j][i - 1]][i - 1];
}
}
}
struct {
pii seg[4 * N];
void build(int l, int r, int i){
if (l == r) return seg[i] = {a[l], l}, void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
pii query(int l, int r, int i, int ll, int rr){
if (l >= ll && r <= rr) return seg[i];
if (r < ll || l > rr) return {0, 0};
int mid = (l + r) / 2;
return max(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
}
} seg;
void init(int nn, std::vector<int> h) {
n = nn;
for (int i = 0; i < n; i++) a[i + 1] = h[i];
seg.build(1, n, 1);
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, jumpleft[i][0] = l[i];
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";
mx[(a[l[i]] > a[r[i]] ? l[i] : r[i])].emb(i);
mn[(a[l[i]] < a[r[i]] ? l[i] : 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 << " : \n";
// cout << "MX : ";
// for (int j = 0; j <= 3; j++) cout << parmx[i][j] << " "; cout << "\n";
// cout << "MN : ";
// for (int j = 0; j <= 3; j++) cout << parmn[i][j] << " "; cout << "\n";
// }
}
int minimum_jumps(int l1, int r1, int l2, int r2) {
l1++, r1++, l2++, r2++;
int u = r1;
pii mxval = seg.query(1, n, 1, l2, r2);
auto [mx, v] = mxval;
if (a[u] > mx) return -1;
for (int i = LG - 1; i >= 0; i--) {
if (jumpleft[u][i] >= l1 && a[jumpleft[u][i]] < a[v]) u = jumpleft[u][i];
}
if (r1 + 1 <= l2 - 1 && seg.query(1, n, 1, r1 + 1, l2 - 1).first > mx) return -1;
int ans = 0;
if (r[u] < l2) {
for (int i = LG - 1; i >= 0; i--) {
if (a[parmx[u][i]] < mx && r[parmx[u][i]] < l2) u = parmx[u][i], ans += (1 << i);
}
if (a[parmx[u][0]] < mx) u = parmx[u][0], ans++;
for (int i = LG - 1; i >= 0; i--) {
if (a[parmn[u][i]] < mx && r[parmn[u][i]] < l2) u = parmn[u][i], ans += (1 << i);
}
}
if (r[u] >= l2 && r[u] <= r2) return ans + 1;
else return -1;
}
