#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
#define cerr if(0) cout
ll n, l;
vec<int> a;
vec<vec<ll>> up, upR, upL;
void init(int N, std::vector<int> H) {
n = N + 2;
a = {INT_MAX};
for(int &x : H) a.push_back(x);
a.push_back(INT_MAX);
up.assign(n,vec<ll>(20,-1));
upR.assign(n,vec<ll>(20,-1));
upL.assign(n,vec<ll>(20,-1));
stack<ll> st;
for(int i = 0; i < n; i++) {
while(!st.empty() and a[st.top()] <= a[i]) st.pop();
upL[i][0] = (st.empty() ? i : st.top());
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n-1; i >= 0; i--) {
while(!st.empty() and a[st.top()] <= a[i]) st.pop();
upR[i][0] = (st.empty() ? i : st.top());
st.push(i);
}
for(ll i = 0; i < n; i++) {
up[i][0] = (a[upL[i][0]] > a[upR[i][0]] ? upL[i][0] : upR[i][0]);
}
for(ll i = 1; i < 20; i++) {
for(ll v = 0; v < n; v++) {
up[v][i] = up[up[v][i-1]][i-1];
upL[v][i] = upL[upL[v][i-1]][i-1];
upR[v][i] = upR[upR[v][i-1]][i-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
ll at = B;
A++;B++;C++;D++;
// edge case: no middle
if(C == B+1) {
if(upR[at][0] > D) return -1;
return 1;
}
// find the midpeak
ll midPeak = B+1;
for(ll i = 19; i >= 0; i--) {
if(upR[midPeak][i] < C) {
midPeak = upR[midPeak][i];
}
}
cerr << "Midpeak: " << midPeak << " w/ " << a[midPeak] << endl;
// edge case: we are already taller than this
if(a[B] >= a[midPeak]) {
cerr << "Taller than mid, returning" << endl;
if(upR[at][0] > D) return -1;
return 1;
}
// find best starting poll from this
for(ll i = 19; i >= 0; i--) {
if(upL[at][i] >= A and a[upL[at][i]] < a[midPeak]) {
at = upL[at][i];
}
}
cerr << "New starting poll: " << at << " w/ " << a[at] << endl;
// edge case: next best peak brings us right there
if(A <= upL[at][0] and upR[ upL[at][0] ][0] <= D and C <= upR[ upL[at][0] ][0]) {
cerr << "Oh we can go back one and skip" << endl;
return 1;
}
ll ans = 0;
cerr << "Stupid cases done, binlifting to mid" << endl;
// binlift us up to mid yay
for(ll i = 19; i >= 0; i--) {
// cerr << up[at][i] << endl;
cerr << "up[" << at << "][" << i << "]:" << up[at][i] << endl;
if(a[up[at][i]] <= a[midPeak]) {
at = up[at][i];
ans += (1<<i);
}
}
cerr << "After binlift at is " << at << " with " << a[at] << " spent " << ans << endl;
if(at == midPeak) {
if(upR[at][0] <= D) return ans + 1;
return -1;
}
// if we are NOT at mid check the going left case
if(at != midPeak) {
cerr << "Not at mid so check left " << endl;
if(upL[at][0] > 0 and upR[ upL[at][0] ][0] <= D) return ans + 2;
}
// going left doesnt work so go right
for(int i = 19; i >= 0; i--) {
if(upR[at][i] < C) {
at = upR[at][i];
ans += (1<<i);
}
}
if(C <= upR[at][0] and upR[at][0] <= D) return ans + 1;
return -1;
}
