#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;
H.push_back(1e9);
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+1);
mn[i].resize(N+1);
}
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] = N;
}
}
mx[0][N] = mn[0][N] = N;
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;(A!=C) && (k>=0);k--){
if (H[mx[k][A]] <= H[C]){
A = mx[k][A];
ans += (1 << k);
}
}
for (int k=lg-1;(A!=C) && (k>=0);k--){
if (H[mn[k][A]] <= H[C]){
A = mn[k][A];
ans += (1 << k);
}
}
if (A == C){
return ans;
}
return -1;
}
