#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> H;
int lg;
vector<vector<int>> out;
vector<vector<int>> mn,mx;
void init(int N2, std::vector<int> H2){
N=N2;
H=H2;
stack<int> s;
out.resize(N);
for (int i=0;i<N;i++){
while (s.size() && H[s.top()] < H[i]){
out[s.top()].push_back(i);
s.pop();
}
s.push(i);
}
while (s.size()) s.pop();
for (int i=N-1;i>=0;i--){
while (s.size() && H[s.top()] < H[i]){
out[s.top()].push_back(i);
s.pop();
}
s.push(i);
}
lg = log2(N) + 1;
mx.resize(lg);
mn.resize(lg);
for (int i=0;i<lg;i++){
mx[i].resize(N);
mn[i].resize(N);
}
for (int i=0;i<N;i++){
if (out[i].size() == 1){
mx[0][i] = mn[0][i] = out[i][0];
} else if (out[i].size() == 2){
int a = out[i][0], b = out[i][1];
if (H[a] > H[b]) swap(a,b);
mn[0][i] = a;
mx[0][i] = b;
} else {
mn[0][i] = mx[0][i] = i;
}
}
for (int i=1;i<lg;i++){
for (int j=0;j<N;j++){
mx[i][j] = mx[i-1][mx[i-1][j]];
mn[i][j] = mn[i-1][mn[i-1][j]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0;
for (int k=lg-1;k>=0;k--){
if (H[mx[k][A]] < H[C]){
A = mx[k][A];
ans += (1 << k);
}
}
for (int k=lg-1;k>=0;k--){
if (H[mn[k][A]] < H[C]){
A = mn[k][A];
ans += (1 << k);
}
}
if (mn[0][A] == C || mx[0][A] == C){
return ans+1;
}
return -1;
}
