#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 210000;
const int LOGN = 20;
int n, h[N], l[N], r[N], p1[N], p2[N], p3[N], d1[N], d2[N], jmp1[N][LOGN], jmp2[N][LOGN], jmp3[N][LOGN], ti[N], to[N], tc;
vector<int> cand_l[N], cand_r[N], g1[N], g2[N], g3[N];
void dfs1(int v) {
d1[v] = (p1[v] == -1 ? 0 : d1[p1[v]] + 1);
jmp1[v][0] = (p1[v] == -1 ? v : p1[v]);
for (int k = 1; k < LOGN; k++)
jmp1[v][k] = jmp1[jmp1[v][k - 1]][k - 1];
ti[v] = to[v] = v;
for (int u : g1[v]) {
dfs1(u);
ti[v] = min(ti[v], ti[u]);
to[v] = max(to[v], to[u]);
}
}
void dfs2(int v) {
d2[v] = (p2[v] == -1 ? 0 : d2[p2[v]] + 1);
jmp2[v][0] = (p2[v] == -1 ? v : p2[v]);
for (int k = 1; k < LOGN; k++)
jmp2[v][k] = jmp2[jmp2[v][k - 1]][k - 1];
for (int u : g2[v])
dfs2(u);
}
void dfs3(int v) {
jmp3[v][0] = (p3[v] == -1 ? v : p3[v]);
for (int k = 1; k < LOGN; k++)
jmp3[v][k] = jmp3[jmp3[v][k - 1]][k - 1];
for (int u : g3[v])
dfs3(u);
}
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; i++)
h[i] = H[i - 1];
stack<int> st;
for (int i = 1; i <= n; i++)
l[i] = r[i] = -1;
for (int i = 1; i <= n; i++) {
while (!st.empty() && h[st.top()] < h[i]) {
r[st.top()] = i;
st.pop();
}
if (!st.empty())
l[i] = st.top();
st.push(i);
}
for (int i = 1; i <= n; i++) {
if (l[i] != -1)
cand_r[l[i]].push_back(i);
if (r[i] != -1)
cand_l[r[i]].push_back(i);
p1[i] = p2[i] = -1;
p3[i] = r[i];
if (p3[i] != -1)
g3[p3[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
sort(begin(cand_l[i]), end(cand_l[i]), [&](int i, int j) {return h[i] > h[j];});
sort(begin(cand_r[i]), end(cand_r[i]), [&](int i, int j) {return h[i] > h[j];});
if (!cand_l[i].empty()) {
int v = cand_l[i][0];
g1[i].push_back(v);
p1[v] = i;
if (l[v] != -1) {
g2[l[v]].push_back(v);
p2[v] = l[v];
}
}
if (!cand_r[i].empty()) {
int v = cand_r[i][0];
g1[i].push_back(v);
p1[v] = i;
if (r[v] != -1) {
g2[r[v]].push_back(v);
p2[v] = r[v];
}
}
}
tc = 0;
for (int i = 1; i <= n; i++) {
if (p1[i] == -1) dfs1(i);
if (p2[i] == -1) dfs2(i);
if (p3[i] == -1) dfs3(i);
}
}
bool is_anc(int a, int b) {
return ti[a] <= b && b <= to[a];
}
int solve(int a, int b) {
int ans = 0;
for (int k = LOGN - 1; k >= 0; k--)
if (d2[a] - (1 << k) >= 0 && d1[jmp2[a][k]] >= d1[b]) {
ans += (1 << k);
a = jmp2[a][k];
}
for (int k = LOGN - 1; k >= 0; k--)
if (d1[a] - (1 << k) >= 0 && d1[jmp1[a][k]] >= d1[b]) {
ans += (1 << k);
a = jmp1[a][k];
}
return ans;
}
int lca(int a, int b) {
if (d1[a] < d1[b])
swap(a, b);
for (int k = LOGN - 1; k >= 0; k--)
if (d1[a] - (1 << k) >= d1[b])
a = jmp1[a][k];
if (a == b)
return a;
for (int k = LOGN - 1; k >= 0; k--)
if (jmp1[a][k] != jmp1[b][k]) {
a = jmp1[a][k];
b = jmp1[b][k];
}
return p1[a];
}
int minimum_jumps(int a, int b, int c, int d) {
a++; b++; c++; d++;
int ta = max(a, ti[lca(c, d)]), tb = b;
if (tb < ta) return -1;
ta = lca(ta, tb);
int tt = ta;
for (int k = LOGN - 1; k >= 0; k--)
if (jmp3[tt][k] < c)
tt = jmp3[tt][k];
tt = p3[tt];
if (tt < c || d < tt) return -1;
int x = solve(ta, tt);
if (l[tt] == -1 || r[l[tt]] == -1) return x;
tt = r[l[tt]];
if (tt < c || d < tt) return x;
int y = solve(ta, tt);
if (x == -1) return y;
if (y == -1) return x;
return min(x, y);
}
