#include "jumps.h"
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int n, k;
vector<int> h, idx;
vector<vector<int>> st_max, st_nxt;
void init(int N, vector<int> H) {
n = N;
h = H;
k = __lg(n) + 1;
idx.resize(n);
for (int i = 0; i < n; i++) {
h[i]--;
idx[h[i]] = i;
}
st_max.resize(k, vector<int>(n));
stack<int> s;
for (int i = 0; i < n; i++) {
while (not s.empty() and s.top() <= h[i]) s.pop();
st_max[0][i] = s.empty() ? h[i] : s.top();
s.push(h[i]);
}
while (not s.empty()) s.pop();
st_nxt.resize(k, vector<int>(n));
for (int i = n - 1; i >= 0; i--) {
while (not s.empty() and s.top() <= h[i]) s.pop();
st_max[0][i] = max(st_max[0][i], s.empty() ? h[i] : s.top());
st_nxt[0][i] = s.empty() ? h[i] : s.top();
s.push(h[i]);
}
for (int i = 1; i < k; i++) {
for (int j = 0; j < n; j++) {
st_max[i][j] = st_max[i - 1][idx[st_max[i - 1][j]]];
st_nxt[i][j] = st_nxt[i - 1][idx[st_nxt[i - 1][j]]];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
int ans = 0;
for (int bit = k - 1; bit >= 0; bit--) {
if (st_max[bit][a] < h[d]) {
ans += (1 << bit);
a = idx[st_max[bit][a]];
}
}
for (int bit = k - 1; bit >= 0; bit--) {
if (st_nxt[bit][a] < h[d]) {
ans += (1 << bit);
a = idx[st_nxt[bit][a]];
}
}
return (st_nxt[0][a] == h[d] ? ans + 1 : -1);
}
