#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include "jumps.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z){
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
#define nl "\n"
#define sp << " " <<
/********* DEBUG *********/
const ll MOD = 1000000007;
const ll inf = 1e18;
const ll mxN = 1000005;
vector<int> heights(2000005);
int n;
// greedy jump to bigger one, never jump to bigger than max((c to d))
vector<ll> pref(2000005), suff(2000005);
void init(int N, vector<int> H) {
n=N;
heights.resize(n);
pref.resize(n);
suff.resize(n);
for (int i = 0; i < n; i++)
heights[i] = H[i];
// [height, idx]
stack<pair<ll, ll>> st;
for (int i = 0; i < n; i++){
while (st.size() && st.top().first < heights[i])
st.pop();
if (st.empty())
pref[i] = -1;
else
pref[i] = st.top().second;
st.push({heights[i], i});
}
while(st.size())
st.pop();
for (int i = n-1; i >= 0; i--){
while (st.size() && st.top().first < heights[i])
st.pop();
if (st.empty())
suff[i] = -1;
else
suff[i] = st.top().second;
st.push({heights[i], i});
}
// outvec(pref);
// outvec(suff);
}
int minimum_jumps(int A, int B, int C, int D) {
ll peak = 0;
for (int i = C; i <= D; i++){
peak = max(peak, (ll)heights[i]);
}
ll ans = INT_MAX;
for (int i = A; i <= B; i++){
ll ptr = i, moves = 0;
bool reach = false;
while (true){
//outval("ptr:",ptr);
bool flag = false;
ll hl = pref[ptr] == -1 ? -1 : heights[pref[ptr]];
ll hr = suff[ptr] == -1 ? -1 : heights[suff[ptr]];
if (hl > peak)
hl = -1;
if (hr > peak)
hr = -1;
//outval("hl,hr:",hl,hr);
if (hr != -1 && (hr > hl || (suff[ptr] >= C && suff[ptr] <= D)))
ptr = suff[ptr], moves++, flag = true;
else if (hl != -1 && hl > hr)
ptr = pref[ptr], moves++, flag = true;
if (ptr >= C && ptr <= D){
reach = true;
break;
}
if (!flag)
break;
}
if (reach)
ans = min(ans, moves);
}
return ans == INT_MAX ? -1 : ans;
}
