#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXLOG = 18;
const int MAXN = 2e5 + 10;
int binl[MAXLOG][MAXN];
int onlyr[MAXLOG][MAXN];
int n;
vector<int> h;
vector<int> l;
vector<int> r;
void init(int32_t N, vector<int32_t> H) {
n = N;
h.resize(n);
for (int i = 0; i < n; i++) h[i] = H[i];
l.resize(n);
r.resize(n);
stack<pii> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && (s.top().fr < h[i])) s.pop();
if (s.empty()) l[i] = -1;
else l[i] = s.top().se;
s.push({h[i], i});
}
while (!s.empty()) s.pop();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && (s.top().fr < h[i])) s.pop();
if (s.empty()) r[i] = -1;
else r[i] = s.top().se;
s.push({h[i], i});
}
for (int i = 0; i < n; i++) {
if ((l[i] == -1) && (r[i] == -1)) binl[0][i] = i;
else if (l[i] == -1) binl[0][i] = r[i];
else if (r[i] == -1) binl[0][i] = l[i];
else if (h[l[i]] < h[r[i]]) binl[0][i] = r[i];
else binl[0][i] = l[i];
// calc onlyr
if (r[i] == -1) onlyr[0][i] = i;
else onlyr[0][i] = r[i];
}
for (int j = 1; j < MAXLOG; j++) {
for (int i = 0; i < n; i++) {
binl[j][i] = binl[j - 1][binl[j - 1][i]];
onlyr[j][i] = onlyr[j - 1][onlyr[j - 1][i]];
}
}
//for (int i = 0; i < n; i++) cout << l[i] << " " << r[i] << "\n";
return;
}
const int INF = 0x3f3f3f3f;
int32_t minimum_jumps(int32_t a, int32_t x, int32_t b, int32_t y) {
// go from a to b
if (h[a] > h[b]) return -1;
int cost = 0;
for (int i = MAXLOG - 1; i >= 0; i--) {
if (h[binl[i][a]] < h[b]) {
//cout << a << " to " << binl[i][a] << "\n";
a = binl[i][a];
cost += (1LL << i);
}
}
for (int i = MAXLOG - 1; i >= 0; i--) {
if (h[onlyr[i][a]] < h[b]) {
cout << a << " to " << onlyr[i][a] << "\n";
a = onlyr[i][a];
cost += (1LL << i);
}
}
if (r[a] != b) return -1;
return (cost + 1);
}
