#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<int> adj[2002];
long long G[2002][2002];
int up[200002][20];
void init(int N, std::vector<int> H) {
stack<int> st;
for(int i = 0; i <= N; i++){
for(int j = 0; j < 20; j++){
up[i][j] = N;
}
}
for (int i = N - 1; i >= 0; i--) {
while (!st.empty() && H[st.top()] < H[i]) st.pop();
if (!st.empty()) up[i][0] = st.top();
st.push(i);
}
for(int j = 1; j < 20; j++){
for(int i = 0; i < N; i++){
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
// for(int i = 0; i < N; i++){
// for(int j = 0; j < 20; j++){
// cerr << "up[" << i << "][" << j << "] = " << up[i][j] << endl;
// }
// }
}
int minimum_jumps(int A, int B, int C, int D) {
int dist = 0;
for(int i = 19; i >= 0; i--){
if(up[A][i] <= D){
// cerr << i << endl;
A = up[A][i];
dist |= (1 << i);
}
}
if(A != D) dist = -1;
return dist;
}
