#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 500'005;
int n;
vector<vector<int>> edgelist;
vector<vector<int>> pow2parent;
void init(int N, std::vector<int> H) {
n = N;
edgelist = vector<vector<int>> (N+2);
pow2parent = vector<vector<int>> (N+2, vector<int> (20, 0));
set<int> trees;
trees.insert(0);
trees.insert(N+1);
set<int> hanging_trees;
hanging_trees.insert(0);
hanging_trees.insert(-N-1);
vector<pii> heightmap;
vector<int> newH(N+2, 0);
for (int i=0; i<N; i++)
{
heightmap.push_back({H[i], i+1});
newH[i+1] = H[i];
}
sort(heightmap.begin(), heightmap.end());
for (int ind=N-1; ind>=0; ind--)
{
int next_tall = heightmap[ind].second;
int aa = 0 - *(hanging_trees.lower_bound(0-next_tall));
int bb = *( trees.lower_bound( next_tall));
edgelist[next_tall].push_back(aa);
edgelist[next_tall].push_back(bb);
hanging_trees.insert(0-next_tall);
trees.insert(next_tall);
int parent;
if (newH[aa] >= newH[bb])
parent = aa;
else
parent = bb;
pow2parent[next_tall][0] = parent;
for (int i=1; i<=19; i++)
pow2parent[next_tall][i] = pow2parent[ pow2parent[next_tall][i-1] ][i-1];
}
}
bool went_too_high(int node, int C)
{
if (node <= 0)
return 1;
if (node >= (n+1))
return 1;
if ((edgelist[node][0] < C) and (C < edgelist[node][1]))
return 1;
return 0;
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
int jumps_so_far = 0;
int curr = A;
for (int pow = 19; pow>=0; pow--)
{
int candidate = pow2parent[curr][pow];
if (went_too_high(candidate, C) == 0)
{
jumps_so_far = jumps_so_far + (1<<pow);
curr = candidate;
}
}
if (edgelist[curr][0] == C)
return jumps_so_far+1;
if (edgelist[curr][1] == C)
return jumps_so_far+1;
return -1;
}
