#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
const int N = 2e5 + 5;
int n;
arr<int, N> h;
arr<int, N> l, r;
arr<arr<int, 22>, N> jmp1, jmp2;
void prcmp() {
stack<int> ord;
for (int i = 1; i <= n; i++) {
while (ord.size() && h[ord.top()] < h[i]) ord.pop();
if (ord.size()) l[i] = ord.top();
ord.push(i);
}
while (ord.size()) ord.pop();
for (int i = n; i >= 1; i--) {
while (ord.size() && h[ord.top()] < h[i]) ord.pop();
if (ord.size()) r[i] = ord.top();
ord.push(i);
}
for (int u = 1; u <= n; u++) {
jmp1[u][0] = (h[l[u]] > h[r[u]]) ? l[u] : r[u];
jmp2[u][0] = r[u];
}
for (int i = 1; i <= 20; i++)
for (int u = 1; u <= n; u++)
jmp1[u][i] = jmp1[jmp1[u][i - 1]][i - 1], jmp2[u][i] = jmp2[jmp2[u][i - 1]][i - 1];
// for (int i = 1; i <= n; i++) cout << l[i] << " " << r[i] << endl;
// for (int i = 1; i <= n; i++) cout << jmp1[i][0] << endl;
}
void init(int _n, vector<int> _h) {
n = _n;
for (int i = 1; i <= n; i++) h[i] = _h[i - 1];
prcmp();
}
vct<int> lft1(int u, int x) {
int dst = 0;
for (int i = 20; i >= 0; i--)
if (jmp1[u][i] != 0 && h[jmp2[u][i]] <= x)
u = jmp1[u][i], dst += (1 << i);
return {u, dst};
}
vct<int> lft2(int u, int x) {
if (h[u] >= x) return {u, 0};
int dst = 0;
for (int i = 20; i >= 0; i--)
if (jmp2[u][i] != 0 && h[jmp2[u][i]] < x)
u = jmp2[u][i], dst += (1 << i);
u = jmp2[u][0], dst++;
return {u, dst};
}
int minimum_jumps(int _u1, int _u2, int _v1, int _v2) {
assert(_u1 == _u2 && _v1 == _v2);
int u = _u1 + 1, v = _v1 + 1;
if (h[u] > h[v]) return -1;
int w = lft1(u, h[v])[0], dst1 = lft1(u, h[v])[1];
assert(h[w] <= h[v]);
int x = lft2(w, h[v])[0], dst2 = lft2(w, h[v])[1];
assert(x == 0 || h[x] >= h[v]);
if (x == 0 || h[x] > h[v]) return -1;
assert(x == v);
return dst1 + dst2;
}
