#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<int> H;
constexpr ll PW = 262144;
constexpr ll LOG = 20;
struct segment {
vector<ll> seg;
segment() {
seg.assign(2 * PW, 1e9);
}
void update(int x, ll d) {
x += PW;
seg[x] = d;
x /= 2;
while (x >= 1) {
seg[x] = min(seg[2 * x], seg[2 * x + 1]);
x /= 2;
}
}
ll query(int l, int r) {
l += PW; r += PW;
ll sol = 1e9;
while (l <= r) {
if (l % 2 == 1) {
sol = min(sol, seg[l]);
l ++;
}
if (r % 2 == 0) {
sol = min(sol, seg[r]);
r --;
}
l /= 2; r /= 2;
}
return sol;
}
void clear() {
for (int i = 0; i < 2 * PW; i ++) seg[i] = 1e9;
}
};
struct binlift {
int N, LOG;
vector<int> p;
vector<int> depth;
vector<vector<int>> bl;
vector<vector<int>> adj;
binlift() {}
binlift(int N_, int LOG_, vector<int> p_) {
N = N_;
LOG = LOG_;
p = p_;
depth.resize(N);
bl.assign(LOG_, vector<int>(N));
adj.resize(N);
for (int i = 0; i < N; i ++) {
if (p[i] != -1) adj[p[i]].push_back(i);
}
for (int i = 0; i < N; i ++) {
if (p[i] == -1) {
depth[i] = 0;
dfs_depth(i);
}
}
for (int i = 0; i < N; i ++) {
bl[0][i] = (p[i] != -1) ? p[i] : i;
}
for (int p = 1; p < LOG; p ++) {
for (int i = 0; i < N; i ++) {
bl[p][i] = bl[p - 1][bl[p - 1][i]];
}
}
// for (int p = 0; p < LOG; p ++) {
// cout << "p : " << p << " -> ";
// for (int i = 0; i < N; i ++) cout << bl[p][i] << " ";
// cout << '\n';
// }
}
void dfs_depth(int u) {
for (auto x : adj[u]) {
depth[x] = depth[u] + 1;
dfs_depth(x);
}
}
int n_th_ancestor(int u, int n) {
// cout << "n, u : " << n << " " << u << '\n';
for (int i = LOG - 1; i >= 0; i --) {
if (n & (1 << i)) {
// cout << "2 ^ " << i << " esimo parent di " << u << '\n';
u = bl[i][u];
}
// cout << "-> " << u << '\n';
}
return u;
}
};
segment seg;
vector<int> p_max;
vector<int> p_dx;
binlift bl_max, bl_dx;
void init(int N, vector<int> H) {
::N = N;
::H = H;
vector<int> inv_H(N + 1);
for (int i = 0; i < N; i ++) inv_H[H[i]] = i;
p_max.assign(N, -1);
p_dx.assign(N, -1);
// a destra
for (int i = N - 1; i >= 0; i --) {
int u = seg.query(H[i] + 1, N);
if (u != 1e9) {
p_dx[i] = u;
p_max[i] = u;
}
seg.update(H[i], i);
}
seg.clear();
// a sinistra
for (int i = 0; i < N; i ++) {
int u = -seg.query(H[i] + 1, N);
if (u != -1e9) {
if (p_max[i] != -1 && H[u] > H[p_max[i]]) p_max[i] = u;
}
seg.update(H[i], -i);
}
bl_max = binlift(N, LOG, p_max);
bl_dx = binlift(N, LOG, p_dx);
}
int minimum_jumps(int A, int B, int C, int D) {
// A == B e C == D
// cout << "a, c : " << A << " " << C << '\n';
int k = -1;
for (int p = PW; p >= 1; p /= 2) {
// cout << "k, p, k + p : " << k << " " << p << " " << k + p << '\n';
int u = bl_max.n_th_ancestor(A, (p + k));
if (bl_dx.depth[C] > bl_dx.depth[u]) continue;
int v = bl_dx.n_th_ancestor(u, bl_dx.depth[u] - bl_dx.depth[C]);
if (v == C) k += p;
}
if (k == -1) return -1;
int u = bl_max.n_th_ancestor(A, k);
int sol = (bl_dx.depth[u] - bl_dx.depth[C]) + (bl_max.depth[A] - bl_max.depth[u]);
return sol;
}
// int main() {
// int N, Q;
// cin >> N >> Q;
// vector<int> H(N);
// for(int &x: H) cin >> x;
// init(N, H);
// for(int i=0; i<Q; i++){
// int A, B, C, D;
// cin >> A >> B >> C >> D;
// cout << minimum_jumps(A, B, C, D) << "\n";
// }
// }
