#include <bits/stdc++.h>
using namespace std;
// find nearest left, nearest right with monotonic stack (like in prev mock)
// need bin lift table up? need log
// We need to do this: go up left or right
int n;
vector<int> height;
vector<vector<int>> binliftL;
vector<vector<int>> binliftR;
vector<vector<int>> normalLift;
const int LOG = 26;
void init(int n1, vector<int> arr){ // find dominance by using monotonic stack
height = arr;
height.insert(height.begin(), INT_MAX);
height.push_back(INT_MAX);
n = height.size();
vector<vector<int>> inputL(LOG, vector<int>(n));
vector<vector<int>> inputR(LOG, vector<int>(n));
vector<vector<int>> lifter(LOG, vector<int>(n));
stack<int> stck; // start off from 0, so that means the left elements are being comaped to
for(int i = 0; i < n; i++){
while(!stck.empty() && height[stck.top()] <= height[i]){
stck.pop(); // element is less than current ele, can be discarded now
}
if(stck.empty()){
inputL[0][i] = i; // leftmost higher IS itself
}else{
inputL[0][i] = stck.top();
}
stck.push(i);
}
stack<int> stck2;
for(int i = n-1; i >= 0; i--){
while(!stck2.empty() && height[stck2.top()] <= height[i]){
stck2.pop(); // element is less than current ele, can be discarded now
}
if(stck2.empty()){
inputR[0][i] = i; // rightmost higher IS itself
}else{
inputR[0][i] = stck2.top();
}
stck2.push(i);
}
for(int i = 0; i < n; i++){
// just check left and right heights
if(height[ inputL[0][i] ] > height[ inputR[0][i] ]){
lifter[0][i] = inputL[0][i];
}else{
lifter[0][i] = inputR[0][i];
}
}
// bin lift (easy)
for(int k = 1; k < LOG; k++){
for(int i = 0; i < n; i++){
inputL[k][i] = inputL[k-1][ inputL[k-1][i] ];
inputR[k][i] = inputR[k-1][ inputR[k-1][i] ];
lifter[k][i] = lifter[k-1][ lifter[k-1][i] ];
}
}
binliftR = inputR;
binliftL = inputL;
normalLift = lifter;
}
int findIndex(int a, int b){
for(int k = LOG - 1; k >= 0; k--){
if(binliftR[k][a] <= b){
a = binliftR[k][a]; // keep goiung up till either it is invalid
}
}
return a;
}
int minimum_jumps(int a, int b, int c, int d){
// method: first cases:
// 1: INFINITY 5 8 2 9 4 7 INFINITY or else -1s from 1-2 to 6-7. we can jump left potentially: for example, ----- 10 --4-- 7 --9- 11 4->10->11 faster than 4->7->9->11(assuming 11 is the only target)
// how ????
// first steo, we need to check if there is someone who blocks us in the middle (7. 9 here are examples)
// find max in interval B+1 to c-1
// ok, first off greedy:
// if we have some node x that is left of B, it will either get to B (useless) or it will be stuck by something, so we rather
// start with B and simulate jumps left to a node hgiher than middle highest (this is the hurdle we want to clear)
//do not add these jumps. this helps us find the node in the interval which can jump rightwards (cant use max since that would go)
// too far over
// then, simulate a direct rightward jump(s)
// we can continue climbing left or right depending on which one is higher
// bruh we need to compute this
// once we are finished climbing high edge, we check if we ge to the hurlde. (we literally have to have at the very least of this )
// hieght when we want to go rightwards, if we can even get to the middle hurdle
// do 1 right jump
// or do 1 left jump if we are not at the hurlde (we have to try one more time?)
// then check if it clears hurdle and bin lift gives us somewhere <= D
// all other cases: keep goiung right until we can get to c, or if we cant, -1 return
a++;
b++;
c++;
d++; // account for infinities we added
int hurdlePos;
if(b == c-1){
// just take a right, no need to find hurdle
if(binliftR[0][b] <= d){
return 1;
}
return -1;
}
// now we find hurdle
hurdlePos = findIndex(b+1, c-1);
// check if the max IS a hurdle? current B larger than hurdle then we good, just take a right
if(height[b] > height[hurdlePos]){
if(binliftR[0][b] <= d){
return 1;
}
return -1;
}
int curPos = b; // simulate jumps LEFT FIRST
for(int k = LOG - 1; k >= 0; k--){
// check: IF the next left thing is less than a, we cannot take. we continue jumping until we find highest AND LESS THAN HURDLE
if(binliftL[k][curPos] > 0 && height[binliftL[k][curPos]] < height[hurdlePos]){
curPos = binliftL[k][curPos];
}
}
int ans = 0;
// case 1: firect right jump. first take a left jumpr egardless of hurdle. (guarenteed higher tha hurdle for this left hump, since it would)
// already take it in the loop abive, so all we need to check is <= D
if(binliftL[0][curPos] >= a){
if(binliftR[0][ binliftL[0][curPos] ] <= d){
return 1;
}
}else{
for(int k = LOG - 1; k >= 0; k--){
if(height[ normalLift[k][curPos] ] <= height[hurdlePos]){
curPos = normalLift[k][curPos];
ans += 1 << k;
}
}
if(curPos == hurdlePos){
if(binliftR[0][curPos] <= d){
return ans + 1;
}
return -1;
}
// do the left then right again
if(binliftL[0][curPos] >= a && binliftR[0][ binliftL[0][curPos] ] <= d){
return ans + 2; // both jumps count towards our cost
}
}
// last case: right ward . keep going right until we cant, check if it is within c, D
for(int k = LOG - 1; k >= 0; k--){
if(binliftR[k][curPos] < c){ // when we get to rightmost from c, we have to stop and take the smallest step possible (which is most optimal; if it is -1, then we already cant get there)
curPos = binliftR[k][curPos];
ans += 1 << k;
}
}
int LASTPOS = binliftR[0][curPos]; // we use smallest jump ppossible: k = 0
if(LASTPOS >= c && LASTPOS <= d){
return ans + 1;
}
return -1;
}
